Wykazanie, że minimalne usunięcie wierzchołka na wykresie dwustronnym jest NP-całkowite

Rozważ następujący problem, którego instancją wejściową jest prosty wykres i naturalna liczba całkowita . $G$ $k$

Czy istnieje zestaw taki, że jest dwustronny i ? $S \subseteq V(G)$ $G - S$ $|S| \leq k$

Chciałbym pokazują, że problem ten jest -Complete poprzez zmniejszenie albo 3-SAT, -CLIQUE, -DOMINATING nastawy lub -Vertex COVER do niego. $\rm{NP}$ $k$ $k$ $k$

Wierzę, że mogę zredukować do tego problem 3-KOLOROWY, więc będę musiał tylko zobaczyć, jak ograniczyć jeden z wymienionych problemów. Ale ponieważ byłoby to dość niechlujne, zastanawiam się, czy ktoś widzi eleganckie ograniczenie wyżej wymienionych problemów.

Czy istnieje też nazwa tego problemu decyzyjnego?

complexity-theory np-complete reductions Jernej
źródło

Cykl nieparzysty .

Pål GD

Wydaje się to podobne do zestawu wierzchołków sprzężenia zwrotnego . Oznacza to, że chcesz znaleźć minimalny podzbiór wierzchołków do usunięcia, tak aby wynikowy wykres był acykliczny. Wykres acykliczny jest z definicji drzewem (lub lasem), które jest dwustronne.

Nicholas Mancuso,

@NicholasMancuso Nie jest tak podobny. Tak naprawdę to, jak mówię powyżej, problem między dziwnymi cyklami. Lub, jak zauważa Vor, Yannakakis w latach 70. i 80. nazwał usunięcie dwudzielnego węzła (lub wierzchołka).

Pål GD

@ PålGD, zgadzam się. Czułem, że najłatwiejszą redukcją będzie FVS. Jest to jednak zbędne z uwagi na jego definicję „nieparzystego cyklu”.

Nicholas Mancuso

@Jernej: mówisz „... chciałbym pokazać, że ten problem dotyczy NP , redukując go do 3-SAT, k-CLIQUE, ...”. Czy masz na myśli „Chciałbym pokazać, że ten problem jest trudny do zastosowania przy użyciu redukcji z 3-SAT, k-CLIQUE, ...”? (problem jest wyraźnie w NP, ponieważ testowanie, czy wykres jest dwustronny, można wykonać w czasie liniowym)

Vor

Odpowiedzi:

Twój problem jest szczególnym przypadkiem szerszej klasy problemów zwanych problemami usuwania węzłów :

JM Lewis i M. Yannakakis, „Problem usunięcia węzła dla dziedzicznych właściwości jest NP-zupełny”

$\Pi$ $G$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$ $\Pi$

Twoim problemem jest problem usuwania węzłów dla dwustronności , ale (jak zauważył Pal), jest on dziś znany jako problem przejścia cyklu nieparzystego (OCT).

EDYTOWAĆ

Jeśli chodzi o bezpośrednią redukcję, pomyślałem o tej z 3SAT.

$n$ $m$ $x_i, \overline{x_i}$ $n+1$ $x_i$ $x_i$ $\overline{x_i}$ $n$ $x_i$ $\overline{x_i}$ $C_j$ $C_j$

$G$ $n$

wprowadź opis zdjęcia tutaj

Vor
źródło

To nie jest tak naprawdę odpowiedź na pytanie. OP chce jawnie zredukować używając danego problemu. Co więcej, problem znany jest dzisiaj jako Odd Cycle Transversal.

Pål GD

@ PålGD: masz rację.

Vor

Tak, ale nie widzę od razu zmniejszenia z listy problemów OP, choć ... Znam tylko ten, o którym wspomniałeś, autorstwa Yannakakis.

Pål GD

@ PålGD: Pomyślę o innej redukcji, ale szczerze mówiąc, nie jestem pewien, czego dokładnie chce OP (patrz mój komentarz powyżej).

Vor

@Vor Chcę, aby zobaczyć prostą redukcję do jednego z wymienionych problemów. Ten artykuł jest mi znany, ale raczej szukam najbardziej bezpośredniej redukcji.

Jernej