Clique-Width-Ausdrücke mit logarithmischer Tiefe

Wenn wir eine Baumzerlegung eines Graphen mit der Breite , gibt es verschiedene Möglichkeiten, wie wir ihn "schön" machen können. Insbesondere ist bekannt, dass es möglich ist, ihn in eine Baumzerlegung umzuwandeln, bei der der Baum binär ist und seine Höhe beträgt . Dies kann erreicht werden, während die Breite der Zersetzung höchstens . (Siehe zB "Parallele Algorithmen mit optimaler Geschwindigkeit für begrenzte Baumbreite", von Bodlaender und Hagerup). Logarithmische Tiefe ist also eine Eigenschaft einer Baumzerlegung, die wir fast kostenlos erhalten können. $G$ $w$ $O(\log n)$ $3w$

Meine Frage ist, ob es ein ähnliches Ergebnis für clique-width oder vielleicht ein Gegenbeispiel gibt. Mit anderen Worten, gibt es bei einem Gruppenbreitenausdruck für Verwendung von Bezeichnungen immer einen Gruppenbreitenausdruck der Höhe für , der höchstens Bezeichnungen verwendet? Hier wird die Höhe natürlich als die Höhe des Analysebaums des Clique-Width-Ausdrucks definiert. $G$ $k$ $O(\log n)$ $G$ $f(k)$

Wenn eine Aussage ähnlich der obigen nicht bekannt ist, gibt es ein Beispiel für einen Vertex-Graphen mit kleiner Clique-Breite , so dass der einzige Weg, mit -Labels zu konstruieren , darin besteht, einen Ausdruck mit groß zu verwenden Tiefe? $n$ $G$ $k$ $G$ $f(k)$

treewidth parameterized-complexity fixed-parameter-tractable cliquewidth Michael Lampis
quelle

Baumweite / Cliquenweite wikipedia

VZN

Antworten:

Nach einer Weile habe ich eine Antwort in der Literatur gefunden, also poste ich sie hier, falls sie jemand anderem nützlich ist.

Tatsächlich ist es möglich, Clique-Width-Ausdrücke so auszugleichen, dass sie eine logarithmische Tiefe haben. Das Ergebnis ist in der Arbeit "Graphoperationen zur Charakterisierung von Rangbreiten und ausgeglichenen Graphausdrücken" von Courcelle und Kanté, WG '08, angegeben. Ich zitiere Satz 4.4 aus dem Papier:

"Jeder Graph der Clique-Breite oder NLC-Breite ist der Wert einer 3-ausgeglichenen Clique Breiten Expression von Clique-Breite oder NLC-Breite höchstens " $k$ $k \times 2^{k+1}$

Der Haken dabei ist, dass die Anzahl der Etiketten beim Auswuchten exponentiell ansteigt. Es scheint, dass für die Clique-Breite derzeit kein besseres Ergebnis bekannt ist. Dasselbe Papier liefert ein ähnliches Ergebnis mit nur einem konstanten Anstieg der Rangbreite, was jedoch nicht hilft, da der Unterschied zwischen Clique-Breite und Rangbreite im schlimmsten Fall exponentiell sein kann.

Michael Lampis
quelle

Das erste Ergebnis, das sich mit Ausdrücken mit ausgeglichener Cliquebreite befasst, stammt von Courcelle und Vanicat (DAM 131 (1): 129-150, 2003). Die Arbeit der WG'07 verallgemeinert die Techniken in der Arbeit von 2003 und bietet ausreichende Bedingungen für eine Graphalgebra, um ausgeglichene Ausdrücke zu erhalten. Meine Vermutung war, dass wir das exponentielle Aufblähen nicht vermeiden können, aber ich versuche niemals, es zu beweisen oder zu widerlegen. Zumindest kann unsere Technik das exponentielle Aufblasen nicht vermeiden.

M. Kanté