Was ist für Diagramme ohne Nebeneffekte einfach?

31

Die ungefähre Anzahl von Färbungen scheint bei Graphen ohne Nebeneffekte mit dem Algorithmus von Jung / Shah einfach zu sein . Was sind andere Beispiele für Probleme, die bei allgemeinen Diagrammen schwierig, bei geringfügig ausgeschlossenen Diagrammen jedoch einfach sind?

Update 10/24 Es scheint Grohes Ergebnissen zu folgen, dass die FPT-Formel, die auf Diagrammen mit begrenzter Baumbreite getestet werden soll, FPT-Formel ist, die auf kleinen ausgeschlossenen Diagrammen getestet werden soll. Nun stellt sich die Frage, in welcher Beziehung sie zur Nachvollziehbarkeit des Zählens zufriedenstellender Aufgaben einer solchen Formel steht.

Die obige Aussage ist falsch. MSOL ist FPT in Diagrammen mit begrenzter Baumbreite, 3-Färbbarkeit ist jedoch NP-vollständig in ebenen Diagrammen, die geringfügig ausgeschlossen sind.

ds.algorithms graph-theory graph-minor Jaroslaw Bulatow
quelle

23

Das allgemeinste bekannte Ergebnis ist von Grohe. Eine Zusammenfassung wurde im Juli 2010 vorgelegt:

Martin Grohe, Festkommadefinierbarkeit und Polynomzeit auf Graphen mit ausgeschlossenen Minderjährigen , LICS 2010. ( PDF )

Kurz gesagt, jede Aussage, die in der Festkomma-Logik mit dem Zählen ausgedrückt werden kann, hat einen Polynom-Zeit-Algorithmus für Klassen von Graphen mit mindestens einer ausgeschlossenen Nebenfigur. (FP + C ist eine Logik erster Ordnung, die mit einem Festkommaoperator und einem Prädikat erweitert ist, das die Kardinalität definierbarer Mengen von Eckpunkten angibt.) Die Schlüsselidee ist, dass das Ausschließen eines Nebenzeichens es den Graphen in der Klasse ermöglicht, baumartige Zerlegungen anzuordnen, die in der Festkommalogik (ohne zu zählen) definierbar sind.

~~Eine große Klasse von Antworten auf Ihre Frage erhalten Sie, wenn Sie Eigenschaften berücksichtigen, die in FP + C definierbar, aber schwer zu zählen sind.~~

Bearbeiten: Ich bin nicht sicher, ob dies tatsächlich Ihre Frage beantwortet, noch weniger für Ihr Update. Der Verweis auf und die Aussage über Grohes Ergebnis sind korrekt, aber ich denke nicht, dass der durchgestrichene Text für Ihre Frage relevant ist. (Vielen Dank an Stephan Kreutzer, der darauf hingewiesen hat.) Es könnte eine Klarstellung wert sein: Wollen Sie ein Zählproblem, das im Allgemeinen schwierig, aber für Klassen mit geringen Ausnahmen einfach ist, oder ein Entscheidungsproblem?

András Salamon
quelle

1

Interessant ... Ich frage mich, wie diese baumartige Zerlegung für planare Graphen aussieht

Yaroslav Bulatov

2

Ein nützliches Theorem, das ich gefunden habe, ist, dass Eigenschaft in FP + C ausgedrückt werden kann, wenn sie in Polynomzeit auf begrenztem Tw-Graphen entscheidbar ist. Nun stellt sich die Frage, in welcher Beziehung die Komplexität von FP + C-Entscheidungsproblemen zur Komplexität von analogen Zählproblemen steht.

Jaroslaw Bulatow

@Yaroslav: Könnten Sie uns dazu einen Hinweis geben, sobald dieser geschrieben ist? Vielen Dank.

gphilip

3

Lol, ich habe es nicht wirklich entdeckt, ich habe es "gefunden" auf Seite 2 von Grohes "Logik, Graphen und Algorithmen"

Yaroslav Bulatov

18

Eine interessante Eigenschaft von Minor-Closed-Graph-Familien ist, dass sie die Entartung begrenzt haben . Dies bedeutet, dass alle Probleme, die bei Diagrammen mit eingeschränkter Entartung leicht sind, bei Diagrammen aus einer Familie kleinerer Geschlechter leicht sind.

So ist es zum Beispiel normalerweise ein schwieriges Problem, festzustellen, ob ein Graph eine Clique der Größe k enthält, und die besten Algorithmen sind wie . Wenn wir jedoch wissen, dass die Entartung eine Konstante ist, können k-Cliquen in linearer Zeit gefunden werden, dh in der O (n) -Zeit. Auch dazu gibt der Wikipedia-Artikel zum Cliquenproblem Auskunft. (Die genaue Laufzeit ist etwa .) Dieser Algorithmus stammt von Chiba und Nishizeki . $O(n^k)$ $O(k d(G)^k n)$

Weitere Beispiele finden Sie in dieser Antwort von David Eppstein zu MathOverflow auf eine ähnliche Frage zu Graphen mit eingeschränkter Entartung.

Robin Kothari
quelle

5

Mein Artikel auf arxiv.org/abs/1006.5440 enthält einige neuere Ergebnisse zur Auflistung von Cliquen mit geringer Degeneriertheit, einschließlich der etwas besseren Laufzeit

für die Auflistung aller maximalen Cliquen.

O (d n 3^{d / 3})

$O(dn3^{d/3})$

David Eppstein

Ich kann nicht sehen, was eine Beziehung zwischen Minor-Closed (Ihre Antwort) und Minor-ausgeschlossenen Diagrammen (Frage) ist. Auch der Satz aller vollständigen Graphen ist geringfügig geschlossen, aber sie sind nicht von eingeschränkter Entartung.

Saeed

Geringfügig geschlossen = Geringfügig ausgeschlossen. Alle nicht-trivialen Minor-Closed-Graph-Familien weisen eine begrenzte Entartung auf. Ich hätte meiner ursprünglichen Aussage "nicht trivial" hinzufügen sollen.

Robin Kothari

Zuallererst minor closed! = Excluded minor (stattdessen excluded minor

minor closed), ansonsten können Sie viele neue Approximations- und parametrisierte Algorithmen für viele dichte Klassen von Graphen bereitstellen. Was sind auch die nicht trivialen kleinen geschlossenen Graphen? zB Graphen mit einer Baumbreite von höchstens f (| G |) sind trivial oder nicht trivial? oder Klasse von dichten Graphen (die kleiner geschlossen sind und gut geordneten quasi), ist Trivial minor geschlossen oder nicht-triviale? Ihre Definition ist nicht klar, und Leser können nicht erraten , was in Ihrem Verstand (und ein Teil Ihrer Definitionen ist falsch , wie ich am Anfang angegeben).

\subset

$\subset$

Saeed

Ich kann Ihnen sagen, was ich mit einer kleinen geschlossenen Graphenfamilie meine.

ist ein kleinere von

, wenn

kann bezogen werden

durch Löschen Kanten, Löschen oder isolierten Knoten Vertrag Kanten. Eine Diagrammfamilie ist eine Menge ungerichteter, nicht beschrifteter Diagramme

(normalerweise eine unendliche Menge).

ist eine minderjährige geschlossene Familie, wenn für alle

in

auch alle Minderjährigen von

in

. Eine Familie ist nicht trivial, wenn sie nicht aus allen Diagrammen besteht. Graphen von Baumweite

(für konstante

) sind kleinere geschlossene aber Graphen von Baumweite

H

$H$

G

$G$

H

$H$

G

$G$

F

$F$

F

$F$

G

$G$

F

$F$

G

$G$

F

$F$

k

$k$

k

$k$

sind im Allgemeinen nicht minderjährig geschlossen. So verstehe ich es. Ich könnte mich natürlich irren.

f (| G |)

$f(|G|)$

Robin Kothari

15

Als Ergänzung ist eine weitere nützliche Eigenschaft für Algorithmen , die auf kleinere ausgeschlossenen Graphen , dass diese Graphen haben kleine Separatoren . Genauer gesagt wegen

Ein linearer Zeitalgorithmus zum Auffinden eines Trennzeichens in einem Graphen mit Ausnahme eines Nebenzeichens , Bruce Reed und David R. Wood, ACM Transactions on Algorithms, 2009,

gibt es einen linearen Algorithmus einen Separator von Größe zu finden oder eine Algorithmus zu finden , einen Separator der Größe . $O(n^{2/3})$ $O(n^{3/2} + m)$ $O(n^{1/2})$

Separatoren eignen sich gut für dynamische Programmiertechniken , und es wird gezeigt, dass viele NP-vollständige Probleme schnelle Algorithmen mit einem guten Approximationsverhältnis aufweisen, beispielsweise liegt die Lösung innerhalb eines konstanten Faktors des Optimums oder sogar eines PTAS. Planare Graphen und im Allgemeinen begrenzte Gattungsgraphen sind gute Ausgangspunkte, wenn Sie versuchen, Probleme in Graphen mit geringen Ausschlüssen zu lösen.

Hsien-Chih Chang 張顯張顯
quelle

Hast du eine Idee, ob Separatoren beim Zählen der Anzahl der richtigen Farbtöne helfen?

Jaroslaw Bulatow

1

nicht wirklich, vielleicht hilft das von Ian erwähnte Papier besser. Eine Erweiterung des Ergebnisses findet sich in "Approximationsalgorithmen über Kontraktionszerlegung" von denselben Autoren in SODA '07.

Hsien-Chih Chang 張顯張顯

15

$O(1)$

Algorithmic Graph Minor Theory: Zerlegung, Approximation und Färbung von Demaine, Hajiaghayi und Kawarabayashi

Dieser Artikel gibt eine algorithmische Version eine bestimmten (etwas kompliziert zu erklären) Zersetzung für ausgeschlossen geringfügiges Graphen von der Robertson & Seymour Satz gewährleistet, die eine Reihe dieser verbesserten Annäherung Ergebnisse liefern. Schauen Sie sich auch die Referenzen an.

Ian
quelle

Danke, das ist ziemlich faszinierend ... Ich fand eine zugänglichere Beschreibung des Zerlegungsalgorithmus in Grohes "Logik, Graphen und Algorithmen"

Yaroslav Bulatov,

0

$K_5$ $K_{3,3}$

$H$ $H$

$K_t$ $(t-1)$ $K_t$ $(t-1)$ $t− 2$

Rupei Xu
quelle

Was ist für Diagramme ohne Nebeneffekte einfach?

Antworten: