Komplexität der Zählung aller verbundenen Untergraphen

Sei G ein zusammenhängender Graph.

Wie komplex ist es, alle verbundenen Untergraphen zu zählen, wenn es sich bei G um einen der folgenden Typen handelt?

G ist allgemein.

G ist planar.

G ist zweiteilig.

Mir sind keine Strukturen wichtig oder ..., ich muss nur alle verbundenen Untergraphen zählen! Ich interessiere mich auch für die Komplexität, alle verbundenen Untergraphen mit genau k Knoten in G zu zählen.

Hinweise auf Papiere und Bücher sind ebenfalls willkommen!

cc.complexity-theory graph-theory counting-complexity Marjoonjan
quelle

Ist Ihnen bewusst, dass die Liste in der Frage nicht korrekt formatiert ist? meta.cstheory.stackexchange.com/questions/300/… Wenn Sie sich nicht für die Formatierung interessieren, ist das in Ordnung. Ich bin mir jedoch nicht sicher, ob jemand Zeit für die Beantwortung Ihrer Frage aufwenden möchte, wenn Sie keine Zeit für die korrekte Formatierung Ihrer Frage aufwenden möchten. (Ich sage nicht, dass ich die Antwort kenne.)

Tsuyoshi Ito

Interessieren Sie sich auch dafür, verbundene Untergraphen von beliebiger Größe / Reihenfolge / Struktur / ... aufzulisten, oder möchten Sie, dass sie sich über mehrere Bereiche erstrecken, oder etwas anderes?

Anthony Labarre

Es scheint zu funktionieren, verbundene überspannende Untergraphen zu zählen. Seite 32 von Sokals "multivariatem Tutte-Polynom" verbindet das überspannende Subgraph-Polynom mit dem Zuverlässigkeitspolynom, das eine riesige Literatur enthält

Jaroslaw Bulatow

Es tut mir leid, meine vorherige Antwort zur Verwendung von Kirchhoffs Theorem war falsch. Ich habe über ein Einschluss-Ausschluss-Argument nachgedacht, aber das könnte unmöglich sein.

Diego de Estrada

Dieses Papier ist nicht genau das, wonach Sie gefragt haben, aber das Papier und seine Referenzen können bei der Entwicklung einiger Ideen hilfreich sein.

MS Dousti

Antworten:

Walisisch besagt, dass das Problem # P auch im engsten Fall vollständig ist (Zählung der Anzahl der verbundenen Teilgraphen eines planaren zweigliedrigen Graphen). Siehe unten auf Seite 305 in Welsh, Dominic (1997), "Approximate Counting", Surveys in Combinatorics , Bailey, RA, Hrsg., Cambridge University Press, S. 287–324.

Im Zusammenhang frage ich mich jedoch, ob er wirklich verbundene überspannende Untergraphen meint. Und das führt mich zu der Frage, welche Version des Problems Sie haben möchten: verbundene übergreifende Untergraphen, verbundene Untergraphen, die nicht übergreifend sein müssen, oder verbundene induzierte Untergraphen?

David Eppstein
quelle

Dies ist eine Antwort auf Davids Antwort. Ohne dieses Buch noch angeschaut zu haben, würde ich vermuten, dass das Problem darin besteht, verbundene übergreifende Untergraphen zu zählen, da dies der Punkt x = 1 y = 2 des Tutte-Polynoms ist, und der Autor war daran interessiert. Aber in der Tat denke ich, dass diese drei Probleme sich ziemlich leicht durch das Zählen des Problems der zusammenhängenden überspannenden Untergraphen reduzieren lassen. Die folgenden Verkleinerungen sollten entweder für die exakte Zählung oder die Approximation funktionieren, obwohl das Problem für die Approximation meines Erachtens noch offen ist.

$K_A$ $A$

Das Zählen verbundener übergreifender Untergraphen reduziert sich auf das Zählen verbundener induzierter Untergraphen (Skizze): Sei G ein Graph, in dem wir übergreifende Untergraphen zählen möchten. Teilen Sie jede Kante in zwei Teile, so dass es jetzt | V | + | E | gibt Ecken. Befestigen ein $K_A$ $A$

Hier ist eine andere Interpretation der Frage: Was ist mit dem Zählen unbeschrifteter verbundener Untergraphen? Das ist $\#P$

Colin McQuillan
quelle

Du musst keine Clique beifügen, oder? Sie können alles anhängen, das viele verbundene Untergraphen enthält, solange Sie jedem Scheitelpunkt dasselbe anhängen. Sie können also diese Reduzierungen vornehmen und dabei sowohl die Planarität als auch die Zweiteiligkeit bewahren.

David Eppstein