Problemy wielomianowe w klasach grafów zdefiniowanych przez zabronione indukowane cykliczne podgrupy

11

Skrzyżowane z MO .

Niech $C$ będzie klasą grafu zdefiniowaną przez skończoną liczbę zabronionych indukowanych podrożników, z których wszystkie są cykliczne (zawierają co najmniej jeden cykl).

Czy istnieją problemy związane z grafem trudnym dla NP, które można rozwiązać w czasie wielomianowym dla $C$ innego niż Clique i Clique?

Jeśli dobrze pamiętam, jest to niemożliwe dla niezależnego zestawu (chyba że $P=NP$ ).

Szukaj w graphclasses.org nie znalazł żadnego.

Klasa, dla której Clique i Clique cover są wielomianami, to C5, C6, X164, X165, sunlet4, bez trójkątów

Edytować

Negatywne dla IS i Dominacji jest w tym artykule . Strona 2, wykresy $S_{i,j,k}$ .

— joro
źródło

3

W Stefan Kratsch Pascal Schweitzer, wykres Izomorfizm dla wykresu klas charakteryzuje się dwóch zabronionych indukowanych Subgraphs GI jest wielomianem czasu (w łatwy sposób) rozpuszczalny w

wykresy, a także (mniej w łatwy sposób) do

Wykresy

.

(K_{s}, I_{t}) -free

$(K_s, I_t)\text{-free}$

(K_{s}, K_{1, t}) -free

$(K_s, K_{1,t})\text{-free}$

— Marzio De Biasi,

2

Być może najlepiej jest również zanotować pytanie dotyczące MO, jeśli ktoś jest zainteresowany, może chciałby zobaczyć odpowiedzi / komentarze tutaj.

— RB

1

@MarzioDeBiasi, dlaczego nie zamienić komentarza na odpowiedź?

— Saeed,

14

Myślę, że istnieje szereg trudnych problemów, które stają się łatwe dla grafów bez trójkątów; zwłaszcza te dotyczą bezpośrednio trójkątów, takich jak podział na trójkąty (czy G ma podział na trójkąty?). Inne mniej trywialne przykłady obejmują:

Problem stabilnego zestawu cięć (czy G ma niezależny zestaw S, taki że GS jest odłączony?). Zobacz: W przypadku stabilnych sutsetów na wykresach, Discrete Applied Math. 105 (2000) 39-50.
Podstawa grafu przecięcia (Czy G jest grafem przecięcia podzbiorów zbioru podstawowego elementu K?). Patrz: Problem [GT59] w: Garey & Johnson, Computers and Intractability: Przewodnik po teorii kompletności NP.

— Mon Tag
źródło

11

Oto kilka dodatkowych przykładów odpowiedzi Mon Tag:

$G$ $S$ $G-S$ $G$ $S$
Rozpoznawanie trójkątnych wykresów liniowych jest NP-kompletne (patrz tutaj ). Łatwo też zauważyć, że problem ten staje się wielomianowy dla grafów wejściowych wolnych od trójkątów.
$(C_3, C_4, C_5)$

— vb le
źródło

Dziękuję Ci. Niektóre problemy pozostają trudne, a inne nie.

— joro

10

$(K_s,I_t)\text{-free}$ $(K_s,K_{1,t})\text{-free}$

$K_{1,t}$

Po zastanowieniu się nad tym, łatwo jest udowodnić następujące (oryginalne?):

$\{H_1,...H_k\}$ $H_i$ $\mathcal{C}$ $(H_1,...,H_k)\text{-free}$

$(H_1,...,H_k)\text{-free}$ $H_i$ $G_1,G_2$ $r$ $H_i$ $(u,v)$ $G_1,G_2$ $l = \lceil r/3 \rceil$ $l$ $(u,p_1,p_2,...,p_l,v)$ $G'_1, G'_2$ $(H_1,...,H_k)\text{-free}$ $3\lceil r/3 \rceil + 3 > r$ $G_1,G_2$

wprowadź opis zdjęcia tutaj
$G_1$ $(H_1,...,H_k)\text{-free}$ $G'_1$ $H_i$ $r=15$ $G_1$ $l = 5$

Możemy również rozszerzyć wynik ujemny na problem NPC cyklu Hamiltonian, w rzeczywistości jest to bezpośrednia konsekwencja następujących (oryginalnych?):

$k \geq 3$ $G$ $\leq k$

$G$ $v$ $outdeg(v) + indeg(v) \leq 3$ $G$ $G'$ $v$ $indeg(v )=1$ $v$ $indeg(v)=2$ $G'$ $\geq k$ $G''$ $G$

wprowadź opis zdjęcia tutaj

Następstwo: problemy cyklu i ścieżki Hamiltona pozostają NP-kompletne, nawet jeśli są ograniczone do wykresów, gdzie każdy zawiera cykl. $(H_1,...,H_k)\text{-free}$ $H_i$

— Marzio De Biasi
źródło

Dziękuję Ci. to drzewo, więc nie jest cykliczne, czy coś mi brakuje?

K_{1, t}

$K_{1,t}$

— joro

Masz rację! Wpadłem na wynik negatywny ... sprawdź, czy może działać, czy też jest całkowicie błędny: -S: -S

— Marzio De Biasi

Dzięki. Masz więc rzekomy negatywny wynik dla GI AND cyklu Hamiltonian?

— joro

Mam nadzieję, że jest to poprawne, to rozwiąże wiele nieznanych problemów z graphclasses.org.

— joro

1

Tylko nitpick, każdy cykl powinien być taki jak gdzie jest stopniem wierzchołka , w przeciwnym razie twoja część iff nie jest poprawna, może być jest izomorficzna, ale nie .

(m + 1) d_{i}

$(m+1)d_i$

d_{i}

$d_i$

i

$i$

G_{1}, G_{2}

$G_1,G_2$

G_{1}^{'}, G_{2}^{'}

$G'_1,G'_2$

— Saeed

1

MAX-CUT pozostaje NP-kompletny.

Lemma 3.2 simple max-cut jest NP-complete na następujących dwóch klasach wykresów:

wykresy nie zawierające cykli długości co najwyżej , dla każdego . $k$ $k \ge 3$

Dwukrotnie dzielą krawędź.

Z „MAX-CUT i zależności między warstwami na wykresach, Marcin Kamiński”

— joro
źródło

1

Ale prosiłeś o problemy rozwiązane w czasie wielomianowym, prawda?

— Peng O

@PengO rzeczywiście, ale jest to wynik ujemny, więc nie można być wielomianem. Inna odpowiedź pokazuje również negatywne wyniki.

— joro