Twin Width

Die Twin Width (englisch für „Zwillingsweite“) eines ungerichteten Graphen ist eine natürliche Zahl, die angibt, wie ähnlich der gegebene Graph zu einem Co-Graphen ist. Ein Co-Graph ist ein Graph, der mittels wiederholter Verschmelzung von Zwillingen, das sind Knoten mit identischer Nachbarschaft, zu einem einzelnen Knoten reduziert werden kann. Die Twin Width ist durch eine Folge von wiederholtem Verschmelzen der Knoten definiert, die zwar keine Zwillinge sind, aber eine ähnliche Nachbarschaft aufweisen.

Definition

Die Twin Width ist für einen endlichen ungerichtete Graphen $G=(V,E)$ definiert. Dieser verfügt über eine endliche Menge an Knoten $V$, und eine Menge an Kanten $E$, die ungeordnete Paare von Knoten sind. Die Zwillingsweite ist der minimale Knotengrad $d$ der roten Kanten in einer Kontraktionsfolge.

Literatur

• Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant: Twin-width I: Tractable FO model checking. In: Journal of the ACM. 69. Jahrgang, Nr. 1, 2022, S. A3:1–A3:46, doi:10.1145/3486655, arxiv:2004.14789 (englisch). 
• Jan Dreier, Jakub Gajarský, Yiting Jiang, Patrice Ossona de Mendez, Jean-Florent Raymond: Twin-width and generalized coloring numbers. In: Discrete Mathematics. 345. Jahrgang, Nr. 3, 2022, Paper 112746, doi:10.1016/j.disc.2021.112746, arxiv:1602.09052 (englisch). 

• Pierre Bergé, Édouard Bonnet, Hugues Bonnet, Rémi Watrigant: Approximating highly inapproximable problems on graphs of bounded twin-width. 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany. Band 254, LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, S. 10:1–10:15, doi:10.4230/LIPIcs.STACS.2023.10, arxiv:2207.07708 (englisch).