Corte máx. De familia cerrada menor

Es bien sabido que las gráficas planas de una familia cerrada con menores prohibidos , gráficas con ancho de árbol acotado también son gráficas familiares cerradas sin H k como menor.$K_{3,3}, K_{5}$$H_{k}$

Supongo que los gráficos con corte máximo acotado forman gráficos familiares cerrados. Dado el gráfico arbitrariamente que no contiene H como menor, cómo encontrar el corte máximo aproximadamente.$G$$H$

¡Gracias!

Apéndice:

El tema relevante se puede encontrar en Sobre la complejidad del problema Corte máximo Capítulo 6. Gráficos con ancho de árbol acotado. El PTAS comienza con la modificación de la descomposición del árbol sin aumentar su ancho de árbol.

1) es un árbol binario.$T$

2) Si un nodo tiene dos hijos j 1 y j 2 , entonces X i = X j 1 = X j 2 .$i \in I$$j_{1}$$j_{2}$$X_{i}=X_{j1}=X_{j2}$

3) Si un nodo un hijo j , entonces X j ⊂ X i y | X i - X j | = 1 , o X i ⊂ X j y | X j - X i | = 1 .$i \in I$$j$$X_{j} \subset X_{i}$$|X_{i}-X_{j}|=1$$X_{i} \subset X_{j}$$|X_{j}-X_{i}|=1$

En mi opinión, es una modificación muy fuerte, y en realidad no tengo la idea detrás de esta modificación. En la segunda condición, si entendí bien, si hay un nodo con dos vecinos, entonces todos contienen el mismo conjunto de vértices, pero ¿para qué?

$K_5$$K_6$

Vea también este documento y diapositivas del GT 2010 de Marcin Kamiński .

Hay un PTAS para las clases de gráficos libres de H-menor que se desprende de la teoría menor de gráficos algorítmicos en papel : Descomposición, aproximación y coloración de Erik D. Demaine, Mohammad Taghi Hajiaghayi y Ken-ichi Kawarabayashi en FOCS 2005.