Erstellen einer Baumzerlegung mit minimaler Breite in polynomieller Zeit

Bekanntlich besteht eine Baumzerlegung eines Graphen aus einem Baum T mit einem zugehörigen Sack T v ≤ V ( G ) für jeden Eckpunkt v ≤ V ( T ) , der die folgenden Bedingungen erfüllt:$G$$T$$T_v \subseteq V(G)$$v \in V(T)$

1. Jeder Scheitelpunkt von kommt in einem Beutel von T vor .$G$$T$
2. Für jede Kante von gibt es eine Tasche, die beide Endpunkte der Kante enthält.$G$
3. Für jeden Scheitelpunkt , der Beutel enthält , v einen verbundenen Teilbaum induziert T .$v \in V(G)$$v$$T$

Wir können auch die folgende Bedingung verlangen, genannt Magerkeit , aus unserer Zersetzung:

• Für jedes Beutelpaar , T b von T , wenn A ⊆ T a und B ⊆ T b mit | A | = | B | = k , dann gibt es entweder a) k vertex-disjunkte A - B- Pfade in G oder b) der Baum T enthält eine Kante p q auf dem Pfad von Knoten a zu Knoten b, so dass | V $T_a$$T_b$$T$$A \subseteq T_a$$B \subseteq T_b$$|A| = |B| = k$$k$$A-B$$G$$T$$pq$$a$$b$ und die Menge V ( T p ) ∩ V ( T q ) schneidet alles A - B Pfade in G .$|V(T_p) \cap V(T_q)| \leq k$$V(T_p) \cap V(T_q)$$A-B$$G$

Robin Thomas hat gezeigt, dass es immer eine Baumzerlegung mit minimaler Breite gibt, die auch mager ist, und einfachere Beweise für diese Tatsache wurden von mehreren Autoren geliefert, zum Beispiel von Patrick Bellenbaum & Reinhard Diestel .

Was mich interessiert, ist die folgende: Da ein Graph und eine Minimalbreite Baumzerlegung von G können wir eine Minimalbreite finden schlanke Baumzerlegung von G in Polynomzeit?$G$$G$$G$

Die beiden genannten Beweise liefern keine so effiziente Konstruktivität. In der Arbeit von Bellenbaum und Diestel wird erwähnt, dass "ein weiterer (konstruktiverer) kurzer Beweis für den Satz von Thomas in P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universität Hamburg 2000" gegeben wurde. Leider konnte ich das Manuskript nicht online finden und mein Deutsch ist nicht so gut.

$G$$V(G)+1$$G'$$G'$$G$$G$$G$