Jaka jest złożoność tego problemu z grafem?

Biorąc pod uwagę prosty niekierowany wykres $G$ , znajdź podzbiór $A\neq \emptyset$ wierzchołków, taki jak

dla dowolnego wierzchołka $x\in A$ co najmniej połowa sąsiadów $x$ również znajduje się w $A$ i
rozmiar $A$ jest minimalny.

Oznacza to, że szukamy gromady, w której co najmniej połowa sąsiedztwa każdego wewnętrznego wierzchołka pozostaje wewnętrzna. Samo istnienie takiego klastra jest oczywiste, ponieważ cały zestaw wierzchołków $V(G)$ zawsze ma właściwość 1. Ale jak trudno jest znaleźć najmniejszą (niepustą) taką grupę?

Czy istnieje standardowa nazwa tego problemu? Co wiadomo o jego złożoności?

graph-theory graph-algorithms np-hardness Andras Farago
źródło

Wygląda na wariant problemu z zadowalającą partycją . Nie wiem, czy twój wariant jest znany i udowodniono, że jest NPC; ale prawdopodobnie powinna działać redukcja z k-kliki: połącz każdy węzeł

pierwotnego wykresu z

węzłami

„kliki zewnętrznej” o rozmiarze

(każdy węzeł ma swoją zewnętrzną klikę). Wtedy możesz znaleźć nietrywialny zestaw

o rozmiarze

wtedy i tylko wtedy, gdy

v_{i}

$v_i$

k + 1

$k+1$

C_{i}

$C_i$

2 (k + 1)

$2(k+1)$

A

$A$

k

$k$

k

$k$ -klika istnieje na oryginalnym wykresie (musisz wybrać przynajmniej węzeł, ale musisz unikać jakiejkolwiek zewnętrznej kliki). Ale to tylko pomysł; jeśli mam wystarczająco dużo czasu, postaram się sprawdzić, czy redukcja jest prawidłowa.

Marzio De Biasi,

@MarzioDeBiasi Dziękuję, po kilku poszukiwaniach dowiedziałem się, że problem zadowalającej partycji jest rzeczywiście powiązany. Jednak w każdym wariancie, który udało mi się znaleźć, szukają raczej partycji niż pojedynczego zestawu. Nie jest jasne, w jaki sposób są one powiązane. W twojej redukcji, chyba że coś źle zrozumiałem,

klika oryginalnego wykresu nie spełnia definicji, ponieważ każdy węzeł w nim będzie miał

wewnętrznych sąsiadów, ale co najmniej

zewnętrznych sąsiadów, ze względu na dodane zewnętrzne kliki.

k

$k$

k - 1

$k-1$

k + 1

$k+1$

Andras Farago,

Myślę, że ten problem jest znany jako „sojusz obronny”

daniello,

@daniello: świetnie, szukałem w ankiecie IG Yero, JA Rodriguez-Velazquez, „Defensywne sojusze na wykresach: ankieta”, 2013, ale nie znalazłem słowa „połowa”; kiedy będę miał wystarczająco dużo czasu, przeczytam go uważnie; prawdopodobnie problem OP jest już znany!

Marzio De Biasi

Wygląda na to, że sformułowano, że „każdy wierzchołek ma co najmniej tyle sąsiadów w środku, co na zewnątrz”, co jest takie samo jak w pytaniu do zaokrąglenia i możliwe, że uwzględnia / nie uwzględnia samego wierzchołka w liczbie

daniello

Odpowiedzi:

To redukcja z Clique do twojego problemu.

Rozpoczynamy z instancją Clique: wykres i całkowita , niech . $G$ $k$ $V = \{ v_1, v_2,...,v_n\}$

Klika pozostaje NPC nawet pod warunkiem, że (szkic próbny: jeśli następnie dodaj gdzie $max(deg(v_i)) \leq 2(k-1)$ $max(deg(v_i) > 2(k-1)$ $K_t$ i podłącz go do wszystkich węzłów i poproś o klikę o rozmiarze na nowym wykresie). $t = 2(k-1) - max(deg(v_i))$ $G$ $k' = k + t$

Zakładamy więc, że w , . Dla każdego węzła dla którego tworzymy „zewnętrzną” klikę o rozmiarze (każdy węzeł $G$ $max(deg(v_i)) \leq 2(k-1)$ $v_i$ $deg(v_i) < 2(k-1)$ $C_i$ $2(k+1)+1$ sąsiadów). $C_i$ klika ma co najmniej $2(k+1)$

Jeśli jest stopniem , łączymy z węzłami $deg(v_i)$ $v_i$ $v_i$ $2(k-1) - deg(v_i)$ $C_i$ .

W otrzymanym , każde ma stopień ; więc ponieważ należy wybrać co najmniej jeden wierzchołek. $G'$ $v_i$ $2(k-1)$ $|A| \geq k$

Oczywiste jest, że jeśli jeden z wierzchołków jest zawarty w to należy w nim również wstawić co najmniej węzłów. Należy zauważyć, że jeśli oryginalny węzeł ma to należy uwzględnić co najmniej jeden węzeł połączonego , co prowadzi do . $C_i$ $A$ $2(k+1)/2 = k+1$ $deg(v_i) < k-1$ $C_i$ $|A| > k$

Więc możemy zbudować zestaw o minimalnym rozmiarze wtedy i tylko wtedy, gdy zawiera klikę o rozmiarze . $A$ $|A| = k$ $G$ $k$

Przykład zmniejszenia, w którym pytamy, czy wykres reprezentowany przez żółte węzły i pogrubione krawędzie zawiera klikę o rozmiarze (trójkąt). $G$ $k = 3$

Niebieskie węzły (pogrupowane dla lepszej czytelności) to , czerwone krawędzie to połączenia między węzłami o . $K_9$ $G$ $deg(v_i) < 2(k-1)$

Marzio De Biasi
źródło

@WillardZhan: ponieważ każdy wierzchołek

ma stopień

pod względem konstrukcji, więc jeśli

zawiera jeden wierzchołek, musi zawierać co najmniej

sąsiadów (i to samo dotyczy wszystkich wierzchołków

), więc

. „Minimalny rozmiar”

można osiągnąć tylko wtedy, gdy

jest kliką o rozmiarze

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: Dodałem inny warunek do początkowego problemu kliki (ale powinien pozostać NPC) ... Nadal go sprawdzam (nie do końca przekonany, że jest poprawny).

Marzio De Biasi,

Tak, teraz działa idealnie (choć powinno być

k^{'}

$k'$ w wyrażeniu

t

$t$ ). Może powinienem usunąć moje komentarze?

Willard Zhan

@WillardZhan: Myślę, że to prawda, ponieważ w tym akapicie odnoszę się do redukcji z Clique [instancja

(G, k)

$(G,k)$ ] do ograniczenia Clique +

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

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

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

$(G',k')$ ].

t

$t$ is the number of the nodes (clique) to add to G to get the new instance of Clique that stastisfies the constraint.

Marzio De Biasi