Encontrar subgrafías con alto ancho de árbol y grado constante

Me dan un gráfico con un ancho de árbol k y un grado arbitrario, y me gustaría encontrar un subgrafo H de G (no necesariamente un subgrafo inducido) de modo que H tenga un grado constante y su ancho de árbol sea lo más alto posible. Formalmente, mi problema es el siguiente: habiendo elegido un grado limitado d ∈ N , ¿cuál es la "mejor" función f : N → N tal que, en cualquier gráfico G con ancho de árbol k , pueda encontrar (con suerte eficientemente) una subgrafía H de G con grado máximo ≤ $G$ $k$$H$$G$$H$$d \in \mathbb{N}$$f : \mathbb{N} \to \mathbb{N}$$G$$k$$H$$G$$\leq d$y ancho de árbol .$f(k)$

Obviamente, deberíamos tomar ya que no hay gráficos de gran ancho de árbol con un grado máximo < 3 . Para d = 3 Sé que se puede tomar f tal que f ( k ) = Ω ( k 1 / 100 ) o menos, apelando a Chekuri y de Chuzhoy tabla Resultado de la extracción de menor importancia$d \geq 3$$<3$$d = 3$$f$$f(k) = \Omega(k^{1/100})$(y usarlo para extraer un gráfico de grado 3 de alto ancho de árbol, por ejemplo, un muro, como un topológico menor), siendo factible el cálculo de la subgrafía (en RP). Sin embargo, este es un resultado muy poderoso con una prueba elaborada, por lo que se siente mal usarlo para lo que parece un problema mucho más simple: me gustaría encontrar un subgrafo de alto grado de ancho de árbol de grado constante, no uno específico como en su resultado Además, el límite en no es tan bueno como hubiera esperado. Sin duda, se conoce que se puede hacer Ω ( k 1 / 20 ) (hasta renunciar a la eficiencia de la computación), pero yo esperaría algo así como Ω ( k $f$$\Omega(k^{1/20})$$\Omega(k)$. Entonces, ¿ es posible mostrar que, dada una gráfica del ancho de árbol k , hay una subgrafía de G con un grado constante y un ancho de árbol lineal en k ?$G$$k$$G$$k$

También estoy interesado en la misma pregunta para el ancho de ruta en lugar del ancho de árbol. Para el ancho de ruta, no conozco ninguna extracción menor analógica a la cuadrícula, por lo que el problema parece aún más misterioso ...

Vea el artículo de Julia Chuzhoy y yo sobre los sparsifiers de Treewidth. Se demuestra que se puede obtener un subgrafo de grado a lo sumo 3 con treewidth , donde k es la treewidth de G . https://arxiv.org/abs/1410.1016 La prueba es más corta que la de los menores de la cuadrícula, pero todavía no es tan fácil y se basa en varias herramientas anteriores.$\Omega(k/polylog(k))$$k$$G$

Supongamos que se conforme con un objetivo más fácil - grado 4 y treewidth a continuación, lo puede conseguir mucho más fácilmente a través de resultado de Reed y madera en la red como menores de edad. https://arxiv.org/abs/0809.0724$\Omega(k^{1/4})$

Otro resultado fácil que puede obtener es el siguiente, que es un punto de partida para algunas de las pruebas más complicadas. Puede obtener un subgrafo de degre y treewidth Ω ( k / p o l y l o g ( k ) ) . Puede ver el papel espaciador de ancho de árbol para el argumento para lograr esto.$\log^2(k)$$\Omega(k/\mathsf{polylog}(k))$