Clique Problem bei festen Graphen

21

Wie wir wissen, nimmt die Clique-Funktion einen ( überspannenden ) Teilgraphen eines vollständigen Vertex-Graphen und gibt wenn eine Clique enthält . Variablen entsprechen in diesem Fall Kanten von . Es ist bekannt (Razborov, Alon-Boppana), dass diese Funktion für monotone Schaltkreise mit einer Größe von etwa . C L I Q U E ( n , k ) G K n n K n 1 G k K n 3 k n / 2 n kkCLIQUE(n,k)GKnnKn1GkKn3kn/2nk

Was aber, wenn wir einen festen Graphen und die monotone Boolesche Funktion , die eine Teilmenge von Eckpunkten annimmt und ausgibt, wenn einige Eckpunkte in bilden Clique in . Variablen entsprechen in diesem Fall Scheitelpunkten von , und die Funktion ist nur die Standard-Clique-Funktion, ist jedoch auf die übergreifenden Teilgraphen eines festen Graphen . C L I Q U E ( G , k ) S [ n ] 1 k S GGKnCLIQUE(G,k)S[n]1kSGKnG

1. Gibt es Vertex-Graphen für die monotone Schaltkreise mit einer Größe größer als ? Ich glaube nein. G C L I Q U E ( G , k ) n O ( log n )nGCLIQUE(G,k)nO(logn)
2. Ist ein NP-hartes Problem für eine Folge von Graphen ? Ich glaube nein. ( G n : n = 1 , 2 )CLIQUE(Gn,k)(Gn:n=1,2)

Es ist zu beachten, dass, wenn alle maximale Cliquen in , als eine ODER-Funktion von threshold- berechnet werden kann , deren testet, ob . Wenn also , dann hat die gesamte Schaltung eine polynomische Größe. Aber was ist mit Graphen mit einer exponentiellen Anzahl maximaler Cliquen? (Eine Clique ist maximal, wenn kein Vertex hinzugefügt werden kann.) G C L I Q U E ( G , k ) r kC1,,CrGCLIQUE(G,k)rk| S aC i | k r = p o l y ( n )i|SaCi|kr=poly(n)

Es ist möglich, in für einen bestimmten Graphen auf Eckpunkten "einzubetten" . Insbesondere haben Bollobas und Thomason (1981) gezeigt, dass, wenn ein Hadamard-Graph ist, dessen Eckpunkte Teilmengen von , und zwei Eckpunkte und benachbart sind, wennist gerade, dann enthält eine isomorphe Kopie jedes Graphen auf Eckpunkten. Kann diese Tatsache mit Razborovs Untergrenze (von ungefähr ) für kombiniert werden um daraus zu schließen? C L I Q U E ( H , K ) H n = 2 mCLIQUE(m,k)CLIQUE(H,k)Hn=2m[ m ] u v | u v | H G m m k C L I Q U E ( m , k ) C L I Q U E ( H , k )H[m]uv|uv|HGmmkCLIQUE(m,k)CLIQUE(H,k) erfordert monotone Schaltkreise mit einer Größe von ungefähr ? Ein potentielles Problem hierbei ist, dass, obwohl der Graph alle Vertex-Graphen "enthält" , diese Graphen sich nicht auf derselben Menge von Vertices befinden. Und Razborovs Argument verlangt, dass positive und negative Eingaben ( Klassen und Komplemente vollständiger -Partit-Graphen) Graphen auf derselben Menge von Eckpunkten sind. Außerdem sind alle positiven Eingänge ( Klassen) nur isomorphe Kopien ein und derselben festen Klasse. HmkH m( k - 1 )k(k1)k k

3. Irgendwelche Ideen? Hat jemand gesehen, dass solche Probleme in Betracht gezogen werden? Ich meine, Entscheidungsprobleme für Untergraphen eines festen Graphen. Oder sagen wir, das SAT-Problem für Sub-CNFs eines festen (erfüllbaren) CNF (erhalten durch Entfernen einiger Literale)?

Motivation: Probleme dieser Art hängen mit der Komplexität kombinatorischer Optimierungsalgorithmen zusammen. Aber sie scheinen an sich interessant zu sein. Warum sollten wir nach Algorithmen suchen, die für alle Graphen effizient sind ? In der Realität interessieren uns normalerweise die Eigenschaften kleiner Teile eines (großen) Graphen (Straßennetz in einem Land oder Facebook oder ähnliches).

Bemerkung 1: Wenn der Graph ist bipartite , dann der Scheitelpunkt-edge lnzidenzmatrix der Ungleichungen für alle total unimodular und man kann das Cliquenproblem auf induzierten Subgraphen von durch lineare Programmierung lösen . So kann zum bipartite Graphen , hat eine kleine (wenn auch nicht-monotone) -Schaltung. x u + x v1 ( u , v ) E G G C L I Q U E ( G , k )G=(LR,E)xu+xv1(u,v)EGGCLIQUE(G,k)

Bemerkung 2: Ein Hinweis darauf, dass im Fall von zweiteiligen Graphen die Antwort auf Frage 1 "sollte" tatsächlich NEIN lautet, ist, dass das folgende monotone Karchmer-Wigderson-Spiel auf nur Kommunikationsbits benötigt. Lassen die größte Anzahl von Eckpunkten in einem vollständigen bipartiten Subgraphen seine . Alice bekommt eine Menge von roten Knoten, Bob eine Menge von blauen Knoten, so dass . Das Ziel ist es, eine Nichtkante zwischen und .G O ( log n ) k G A B | A | + | B | > k A BGGO(logn)kGAB|A|+|B|>kAB

Stasys
quelle
Weitere Überlegungen (1) Es scheint, als ob Sie ein ähnliches Ergebnis erhalten, wenn Sie eine "Filter" -Funktion definieren, die die gleiche Anzahl von Variablen wie Kanten und "Filter" -Kanten des festen Graphen basierend auf 0/1 Werten der booleschen Variablen hat ... .? Dies kann die Analyse aufgrund der induzierten Diagrammkonstruktion, die sich von den Kanten zu den Scheitelpunkten bewegt, etwas verringern. (2) In Ihre Frage ist eine einfachere Schlüsselfrage eingebettet, die sich allein lohnt. Was sind einige Graphen mit exponentiellen maximalen Cliquen? Das Hadamard-Beispiel mag nicht ausreichen, weil es so "groß" ist.
vzn
Ich habe kürzlich etwas Unähnliches untersucht und bin auf dieses interessante Faktoid gestoßen: "Eine gierige Cliquenzerlegung eines Graphen wird erhalten, indem maximale Cliquen nacheinander aus einem Graphen entfernt werden, bis der Graph leer ist. Wir haben kürzlich gezeigt, dass jede gierige Cliquenzerlegung von ein graph der Ordnung hat bei mostn n 2 / 4 Clique.“ --mcguinnessnn2/4
vzn
@vzn: Zu deiner letzten Frage. Es gibt eine einfache Konstruktion (ich erinnere mich nicht an wen). Nehmen Sie Kopien von vertex-disjunkten "Antidreiecken" (Dreiergruppen von Vertices ohne Kanten dazwischen) und setzen Sie Kanten zwischen alle Vertices von zwei beliebigen Antidreiecken. Die Anzahl der maximalen Cliquen beträgt dann 2 n / 3 , und dies ist optimal (mehr ist nicht möglich). n/32n/3
Stasys
@vzn: Auf McGuinness Ergebnis. Wie ich verstanden habe, zerlegt er alle Kanten in eine kleine Anzahl kantendisjunkter maximaler (Größen-) Cliquen. Es kann jedoch vorkommen, dass die maximale Clique des induzierten Subgraphen in keinem von ihnen liegt. Trotzdem scheint das Ergebnis in die "richtige Richtung" zu gehen.
Stasys
Zu Bemerkung 2 : Wenn Sie sagen, dass Sie nach einer Clique in einer Zweiteilung suchen, meinen Sie damit eine vollständige Zweiteilung?
MassimoLauria

Antworten:

10

Wir untersuchten das Problem, in baumartiger Auflösung zu beweisen, ob ein fester Graph eine Clique der Größe k hat (wobei k normalerweise klein ist). Insbesondere fanden wir heraus, dass für eine große Klasse von Graphen Widerlegungen der Größe n Ω ( k ) erforderlich sind.GkknΩ(k)

Sie finden den Artikel Parametrisierte Komplexität von DPLL-Suchverfahren unter diesem Link .

MassimoLauria
quelle
1
Ein sehr schönes Ergebnis! Tatsächlich stellte sich meine Frage, als ich versuchte, dasselbe Ergebnis für Widerlegungen von baumartigen Schnittebenen (CP) für das (Clique-) Problem zu zeigen. Für baumartige Ableitungen haben wir zwei (nur?) Werkzeuge: (1) Kommunikationskomplexitätsargumente und (2) Player-Delayer-Spiele von Pudlak und Impagliazzo. Bemerkung 2 impliziert, dass (1) für das Clique-Problem (nachweislich) scheitern wird. Gibt es eine Analogie zu (2) im Fall von CP-Beweisen?
Stasys
6

Ich glaube, dieses Papier kann Ihre Fragen beantworten: http://arxiv.org/abs/1204.6484

Die Arbeit definiert Familien von NP-harten 3SAT-Problemen, so dass die Struktur der Formel für jedes n festgelegt wird und die Eingabe die Polarität der Formel ist.

Unter Verwendung der Standardreduktion von 3SAT auf CLIQUE (jede 3CNF-Klausel definiert einen Satz von 8 möglichen Zuweisungen (oder 7 erfüllenden Zuweisungen) mit Kanten zwischen nicht widersprüchlichen Zuweisungen) gibt es ein Diagramm, so dass es nach dem Entfernen eines Scheitelpunkts für jede Klausel ist NP schwer zu finden, die maximale Clique (oder auch nur annähernd ihre Größe, mit Graph-Produkten oder derandomisierten Graph-Produkten)

user15669
quelle
2

Zu Q3 gibt es einige empirische Arbeiten zum "Backbone" und möglichen "Backdoors" von SAT-Problemen. Das Rückgrat ist die Menge der Literale, die in jeder zufriedenstellenden Aufgabe wahr sind. Eine Hintertür in ein SAT-Problem ist eine (hoffentlich kleine) Menge von Variablen, die eine „Abkürzung“ für die Lösung des Problems darstellen. Diese beiden Strukturen wären wahrscheinlich hilfreich und / oder von entscheidender Bedeutung für das Verständnis dessen, was Sie als "Sub-CNFs" oder "CNFs" bezeichnen, bei denen einige Variablen entfernt wurden. aber auch der DP, Davis Putnam-Algorithmus kann als systematische Erforschung vieler "Sub-CNFs" des CNF angesehen werden, um ihn zu lösen.

[1] Backbones und Backdoors in der Zufriedenheit von Kilby et al

vzn
quelle
SS