Max-Cut der kleinen geschlossenen Familie

Es ist bekannt, dass planare Graphen aus einer geschlossenen Familie mit verbotenen Minderjährigen , Graphen mit begrenzter Baumbreite auch Graphen geschlossener Familien ohne H k als Nebenwert sind .$K_{3,3}, K_{5}$$H_{k}$

Ich gehe davon aus, dass Diagramme mit begrenztem Maximalschnitt Diagramme mit geschlossenen Familien bilden. Wenn ein beliebiger Graph , der H nicht als Moll enthält, wie man den maximalen Schnitt ungefähr findet.$G$$H$

Vielen Dank!

Nachtrag:

Das relevante Thema finden Sie unter Über die Komplexität des Maximum-Cut-Problems in Kapitel 6. Diagramme mit begrenzter Baumbreite. Das PTAS beginnt mit einer Änderung der Baumzerlegung, ohne die Baumbreite zu erhöhen.

1) ist ein Binärbaum.$T$

2) Wenn ein Knoten zwei Kinder j 1 und j 2 hat , dann ist X i = X j 1 = X j 2 .$i \in I$$j_{1}$$j_{2}$$X_{i}=X_{j1}=X_{j2}$

3) Wenn ein Knoten ein Kind j hat , dann ist entweder X j ⊂ X i und | X i - X j | = 1 oder X i ⊂ X j und | 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$

Meiner Meinung nach ist es eine sehr starke Modifikation, und tatsächlich habe ich keine Ahnung, was hinter dieser Modifikation steckt. Unter der 2. Bedingung, wenn ich die Richtigkeit verstanden habe, wenn es einen Knoten mit zwei Nachbarn gibt, dann enthalten alle tatsächlich dieselbe Menge der Scheitelpunkte, aber wofür?

$K_5$$K_6$

Siehe auch dieses WG 2010-Papier und Folien von Marcin Kamiński .

Es gibt ein PTAS für h-Moll-freie Klassen von Graphen, das sich aus der Arbeit Algorithmic Graph Minor Theory: Zerlegung, Approximation und Färbung von Erik D. Demaine, Mohammad Taghi Hajiaghayi und Ken-ichi Kawarabayashi in FOCS 2005 ergibt.