Logspace-Algorithmen für Diagramme mit begrenzter Baumbreite

23

Die Baumbreite misst, wie nah ein Diagramm an einem Baum ist. Es ist NP-schwer, die Baumbreite zu berechnen. Der bekannteste Näherungsalgorithmus erreicht Faktor.O(logn)

Courcelles Theorem besagt, dass jede Eigenschaft von Graphen, die in der monadischen Logik zweiter Ordnung (MSO2) definierbar ist, in linearer Zeit für jede Klasse von Graphen mit begrenzter Baumbreite bestimmt werden kann . Ein kürzlich durch Papier zeigte , dass Courcelle Theorem noch hält , wenn „ die lineare Zeit“ mit „logspace“ ersetzt wird. Dadurch wird jedoch die räumliche Komplexität des Diagrammisomorphismus bei Diagrammen mit begrenzter Baumbreite nicht festgelegt. Das bekannteste Ergebnis ist LogCFL.

Gibt es andere Probleme, die sind:

  • NP-hart (oder in P nicht bekannt) in allgemeinen Graphen und
  • bekanntermaßen in linearer / polynomialer Zeit auf Graphen mit begrenzter Baumbreite lösbar sind, und
  • NICHT bekannt, dass sie in LogSpace sind?
Shiva Kintali
quelle
Was ist das im Näherungsfaktor genannte ? n
gphilip
ist die Anzahl der Eckpunkte im Eingabediagramm. n
Shiva Kintali
5
Wir können es im Allgemeinen besser machen als in annähernder Baumbreite. Der beste Algorithmus für die Polynomialzeit-Approximation, von dem ich weiß, dass er einO(O(logn)Approximationsfaktor, wobeiwdie Baumbreite des Graphen ist. Siehe Feige, Hajiaghayi und Lee,Verbesserte Approximationsalgorithmen für Scheitelpunkttrennzeichen mit minimalem Gewicht, STOC 2005.O(logw)w
gphilip

Antworten:

15

Tutte-Polynom ist ein Beispiel.

Dies ist eine Verallgemeinerung des chromatischen Polynoms , das selbst in jeder vernünftigen Formulierung ein # P-hartes Problem darstellt. Im

Auswertung des Tutte-Polynoms für Graphen mit begrenzter Baumbreite , SD Noble, Combinatorics, Probability and Computing, 1998,

O(f(k)n4+ϵ)kn

Es scheint, dass das Problem nicht direkt in MSO2 ausgedrückt werden kann, obwohl ich mit den detaillierten Definitionen nicht vertraut bin ... Ich hoffe, dieses Problem ist das, was Sie brauchen!

Hsien-Chih Chang 張顯 張顯
quelle
Was ist die Funktion f?
Michael Blondin
kO(2(k3+ϵ))
Hsien-Chih Chang 張顯 張顯
8
Makowski sagt, dass "alle in der Literatur untersuchten Graphpolynome SOL-definierbar sind" und gibt eine Formulierung des Tutte-Polynoms in Bezug auf SOL, Seite 15 von "Vom Zoo zur Zoologie: Auf dem Weg zu einer allgemeinen Theorie der Graphpolynome". In "Algorithmische Verwendungen des Feferman-Vaught-Theorems" erweitert er Courcelles Theorem, um die Traktierbarkeit für SOL-definierbare Polynome auf Diagrammen mit begrenzter Baumbreite zu zeigen.
Jaroslaw Bulatow