Gibt es Anwendungen der modularen Graphzerlegung in der TCS / Komplexitätstheorie?

8

Welche Anwendungen der modularen Graphzerlegung gibt es in der TCS / Komplexitätstheorie?

Ich bin besonders an seiner Verwendung in Proofs oder oberen / unteren Grenzen interessiert, wenn es auftritt.

[1] Modulare Graphzerlegung , Wikipedia.

[2] Referenzen für modulare Zerlegung , TCS.SE.

reference-request graph-theory graph-algorithms application-of-theory cc.complexity-theory vzn
quelle
2
Habib und Paul haben eine großartige Umfrage zu den algorithmischen Anwendungen der modularen Zerlegung durchgeführt: dx.doi.org/10.1016/j.cosrev.2010.01.001 . Ich bezweifle jedoch die Anwendbarkeit der modularen Zerlegung auf der negativen Seite (nur eine persönliche voreingenommene Sichtweise).
Yixin Cao
2
k
@ YixinCao eine oder beide dieser Antworten könnten sein.
Suresh Venkat
Die modulare Zerlegung oder zumindest die Identifizierung maximal homogener Cliquen ist wichtig für die Zerlegung klauenfreier Graphen. Ich neige auch dazu zu glauben, dass modulare Zerlegungen für untere Grenzen nicht nützlich sind: Wir können sie schnell finden, und wenn wir dies getan haben, haben wir im Grunde eine Reduktion auf einen kleineren Graphen. Wir können also genauso gut mit dem kleineren Diagramm beginnen.
Andrew D. King
1
Die in dieser Antwort erwähnte Doktorarbeit zeigt Links zur deskriptiven Komplexitätstheorie.
Frafl

Antworten:

11

Habib und Paul haben eine großartige Umfrage zu den algorithmischen Anwendungen der graphmodularen Zerlegung durchgeführt.

k

Mir ist jedoch keine Anwendung der graphmodularen Zerlegung in Beweisen für Untergrenzen bekannt, und ich bezweifle ihre Anwendbarkeit auf der negativen Seite (nur eine persönliche voreingenommene Sichtweise).

Eine letzte Bemerkung. Soweit ich weiß, nutzen die meisten algorithmischen Anwendungen nicht die volle Leistung der modularen Zerlegung von Graphen. Kritische Cliquen sind beispielsweise die Reihenmodule auf der zweiten Ebene eines modularen Zerlegungsbaums (die erste Ebene besteht aus jedem einzelnen Scheitelpunkt). und Zwillinge sind (nicht unbedingt starke) Module, die aus zwei benachbarten Eckpunkten bestehen.

Yixin Cao
quelle
Danke. aus dem H & P Online-Toc, Abschnitt 7, "3 neuartige Anwendungen der modularen Zerlegung" - Musteranpassung / gemeinsame Intervalle zweier Permutationen, vergleichende genomische / perfekte Sortierung durch Umkehrungen, parametrisierte Komplexität und Kernelreduktionen / Cluster-Bearbeitung
vzn