Clique Problem bei festen Graphen

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 . $k$ $CLIQUE(n,k)$ $G\subseteq K_n$ $n$ $K_n$ $1$ $G$ $k$ $K_n$ $3\leq k\leq n/2$ $n^k$

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 . $G\subseteq K_n$ $CLIQUE(G,k)$ $S\subseteq [n]$ $1$ $k$ $S$ $G$ $K_n$ $G$

1. Gibt es Vertex-Graphen für die monotone Schaltkreise mit einer Größe größer als ? Ich glaube nein. $n$ $G$ $CLIQUE(G,k)$ $n^{O(\log n)}$

2. Ist ein NP-hartes Problem für eine Folge von Graphen ? Ich glaube nein. $CLIQUE(G_n,k)$ $(G_n\colon n=1,2\ldots)$

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.) $C_1,\ldots,C_r$ $G$ $CLIQUE(G,k)$ $r$ $k$ $i$ $|S_a\cap C_i|\geq k$ $r=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? $CLIQUE(m,k)$ $CLIQUE(H,k)$ $H$ $n=2^m$ $H$ $[m]$ $u$ $v$ $|u\cap v|$ $H$ $G$ $m$ $m^k$ $CLIQUE(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. $m^k$ $H$ $m$ $k$ $(k-1)$ $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. $G=(L\cup R,E)$ $x_u+x_v\leq 1$ $(u,v)\not\in E$ $G$ $G$ $CLIQUE(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$ $G$ $O(\log n)$ $k$ $G$ $A$ $B$ $|A|+|B|>k$ $A$ $B$

cc.complexity-theory optimization circuit-complexity 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

Clique.“ --mcguinness

n

$n$

n^{2} / 4

$n^2/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

, und dies ist optimal (mehr ist nicht möglich).

n / 3

$n/3$

2^{n / 3}

$2^{n/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

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

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

MassimoLauria
quelle

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

Clique Problem bei festen Graphen

Antworten: