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

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