Was ist die Komplexität dieses Diagrammproblems?

Bei einer einfachen ungerichteten Graphen $G$ , finden sie eine Teilmenge $A\neq \emptyset$ von Eckpunkten, so dass

für jeden Knoten $x\in A$ mindestens die Hälfte der Nachbarn von $x$ ebenfalls in $A$ und
Die Größe von $A$ ist minimal.

Das heißt, wir suchen nach einem Cluster, in dem mindestens die Hälfte der Nachbarschaft jedes internen Scheitelpunkts intern bleibt. Die bloße Existenz eines solchen Clusters ist offensichtlich, da die gesamte Scheitelmenge $V(G)$ immer die Eigenschaft 1 hat. Aber wie schwer ist es, den kleinsten (nicht leeren) solchen Cluster zu finden?

Gibt es einen Standardnamen für dieses Problem? Was ist über seine Komplexität bekannt?

graph-theory graph-algorithms np-hardness Andras Farago
quelle

Es scheint eine Variante des Problems der zufriedenstellenden Partition zu sein. Ich weiß nicht, ob Ihre Variante bekannt ist und sich als NPC erwiesen hat. aber wahrscheinlich sollte eine Reduktion von k-clique funktionieren: Verknüpfe jeden Knoten

v_{i}

$v_i$ des ursprünglichen Graphen mit

k + 1

$k+1$ Knoten einer

C_{i}

$C_i$ "externen Clique" der Größe

2 (k + 1)

$2(k+1)$ (jeder Knoten hat seine externe Clique). Dann können Sie eine nichttriviale Menge

A

$A$ der Größe

k

$k$ genau dann finden, wenn a

k

$k$ -clique existiert im Originaldiagramm (Sie müssen mindestens einen Knoten auswählen, aber Sie müssen jede externe Clique vermeiden). Aber es ist nur eine Idee; Wenn ich genug Zeit habe, versuche ich zu sehen, ob die Reduzierung korrekt ist.

Marzio De Biasi

@MarzioDeBiasi Vielen Dank, nach einiger Suche habe ich herausgefunden, dass das Problem der zufriedenstellenden Partition tatsächlich zusammenhängt. In jeder Variante, die ich finden konnte, suchen sie jedoch nach einer Partition und nicht nach einer einzelnen Menge. Es ist nicht klar, wie sie zusammenhängen. In Ihrer Reduktion entspricht eine

k

$k$ Klasse des Originalgraphen nicht der Definition , es sei denn, ich habe etwas falsch verstanden , da jeder Knoten darin

k - 1

$k-1$ interne Nachbarn, aber aufgrund des hinzugefügten externen Nachbarn mindestens

k + 1

$k+1$ externe Nachbarn hat Cliquen.

Andras Farago

Ich denke, dieses Problem ist als "defensive Allianz" bekannt

daniello

@daniello: toll, ich habe in der Umfrage IG Yero, JA Rodriguez-Velazquez, "Defensive Allianzen in Grafiken: eine Umfrage", 2013 gesucht, aber das Wort "halb" nicht gefunden; Wenn ich genug Zeit habe, werde ich es sorgfältig lesen. Es ist wahrscheinlich, dass das OP-Problem bereits bekannt ist!

Marzio De Biasi

Es scheint so formuliert zu sein, dass "jeder Scheitelpunkt mindestens so viele Nachbarn innen wie außen hat", wie in der Frage bis zur Rundung und möglicherweise einschließlich / nicht einschließlich des Scheitelpunkts selbst in der Zählung

daniello

Antworten:

Dies ist eine Reduktion von Clique zu Ihrem Problem.

Wir beginnen mit einer Instanz von Clique: ein Graph und eine ganze Zahl , lassen . $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$

Clique bleibt NPC auch unter der Einschränkung , dass (Nachweis Skizze: wenn dann addiere ein mit $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ und verbinde es mit allen Knoten von und frage nach einer Clique der Größe im neuen Graphen). $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Wir nehmen also an , dass in . Für jeden Knoten , für die wir eine "externe" Clique erstellen der Größe (jeder Knoten von $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ clique hat mindestens Nachbarn. $C_i$ $2(k+1)$

Wenn ist der Grad der verbinden wir zu Knoten . $deg(v_i)$ $v_i$ $v_i$ $2(k-1) - deg(v_i)$ $C_i$

Im resultierenden hat jedes Grad ; so weil mindestens ein Eckpunkt ausgewählt werden muss. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

Es ist klar, dass, wenn einer der Eckpunkte von in ist, mindestens Knoten darin ebenfalls eingefügt werden müssen. Beachten Sie, dass , wenn ein ursprünglicher Knoten dann wenigstens einen Knoten der verknüpften enthalten sein müssen, was zu . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Wir können also eine Menge der Mindestgröße erstellen genau dann, wenn eine Clique der Größe . $A$ $|A| = k$ $G$ $k$

Ein Beispiel für die Reduktion, bei der wir fragen, ob der Graph der durch die gelben Knoten und die fetten Kanten dargestellt wird, eine Clique der Größe (ein Dreieck) enthält. $G$ $k = 3$

Die blauen Knoten (zur besseren Lesbarkeit gruppiert) sind werden die roten Kanten die Verbindungen zwischen den Knoten von mit . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
quelle

@WillardZhan: Da jeder Scheitelpunkt von

konstruktionsbedingt einen Grad

, muss

, wenn er einen Scheitelpunkt enthält, mindestens

Nachbarn (und die gleichen) enthalten gilt für alle Eckpunkte von

), also

. Die "Mindestgröße"

kann nur erreicht werden, wenn

eine Clique der Größe

G^{'}

$G'$

\geq 2 (k - 1)

$\geq 2(k-1)$

A

$A$

2 (k - 1) / 2 = k - 1

$2(k-1)/2 = k-1$

A

$A$

| A | \geq k

$|A| \geq k$

k

$k$

A

$A$

k

$k$

Marzio De Biasi

@WillardZhan: Ich habe dem Start-Clique-Problem eine weitere Bedingung hinzugefügt (aber es sollte NPC bleiben) ... Ich überprüfe es immer noch (nicht vollständig davon überzeugt, dass es korrekt ist).

Marzio De Biasi

Ja, jetzt funktioniert es perfekt (obwohl es im Ausdruck von

sollte ). Vielleicht werde ich meine Kommentare löschen?

k^{'}

$k'$

t

$t$

Willard Zhan

@WillardZhan: Ich denke, es ist richtig, denn in diesem Absatz beziehe ich mich auf die Reduktion von Clique [Instanz

] auf Clique + Nebenbedingung

[Instanz

ist die Anzahl der Knoten (Clique), die zu G hinzugefügt werden müssen, um die neue Instanz von Clique abzurufen, die die Einschränkung festlegt.

(G, k)

$(G,k)$

m a x (d e g (v_{i})) \leq 2 (k - 1)

$max(deg(v_i)) \leq 2(k-1)$

(G^{'}, k^{'})

$(G',k')$

t

$t$

Marzio De Biasi