Baum-Unabhängigkeitszahl II. Drei-Pfad-Konfigurationen

Eine Drei-Pfad-Konfiguration ist ein Graph, der aus drei paarweise intern disjunkten Pfaden besteht, deren Vereinigung von je zwei einen induzierten Zyklus der Länge mindestens vier bildet. Ein Graph ist 3PC-frei, wenn keiner seiner induzierten Teilgraphen eine Drei-Pfad-Konfiguration ist. Wir zeigen, dass 3PC-freie Graphen eine poly-logarithmische Baum-Unabhängigkeitszahl haben. Genauer gesagt, zeigen wir, dass es eine Konstante c gibt, sodass jeder n-Ecken 3PC-freie Graph eine Baumzerlegung hat, in der jeder Beutel eine Stabilitätszahl von höchstens c (n)² hat. Das impliziert, dass das Problem des maximalen gewichteten unabhängigen Satzes sowie mehrere andere natürliche algorithmische Probleme, die allgemein als NP-schwierig bekannt sind, in quasi-polynomieller Zeit gelöst werden können, wenn der Eingangsgraph 3PC-frei ist.