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

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