Problem cięcia bez H

17

Załóżmy, że otrzymałeś połączony, prosty, niekierowany wykres H.

Problem cięcia bez H jest zdefiniowany następująco:

Biorąc pod uwagę prosty, nieukierowany wykres G, istnieje cięcie (podział wierzchołków na dwa niepuste zbiory, L, R), tak że oba wykresy indukowane przez zestawy cięcia (L i R) nie zawierają izomorficznego subgrafu do H .

Na przykład, gdy H jest wykresem z dwoma wierzchołkami połączonymi pojedynczą krawędzią, problem jest taki sam, jak ustalenie, czy wykres jest dwustronny i czy jest w P.

W przypadku, gdy H jest trójkątem, jest to jak wersja wierzchołka problemu Monochromatic Triangle .

Wydaje mi się, że udało mi się wykazać, że gdy H jest połączone 2 z co najmniej trzema wierzchołkami, problem cięcia bez H jest NP-Complete.

Nie udało mi się znaleźć żadnych odniesień do tego problemu (a więc żadnych wyników).

Czy możemy zrezygnować z warunku 2 połączeń i nadal wykazywać kompletność NP?

Czy ktoś wie o jakichkolwiek znanych wynikach, które sugerowałyby powyższy lub silniejszy wynik (lub uważasz, że mogą być istotne)?

Aryabhata
źródło
1
„Myślę, że udało mi się wykazać, że gdy H jest połączone 2 z co najmniej trzema wierzchołkami, problem cięcia bez H jest NP-Complete”. Czy to oznacza, że ​​dla każdego podwójnie połączonego H z trzema lub więcej wierzchołkami cięcie bez H jest NP-całkowite? Podobnie, jeśli porzucimy 2-łączność, chcemy udowodnić, że dla każdego H z trzema lub więcej wierzchołkami cięcie bez H jest NP-całkowite?
Evgenij Thorstensen,
@Evgenij: Tak, dla każdego takiego H jest to NP-Complete. Jest to więc klasa problemów NP-Complete. Tak, na inne pytanie.
Aryabhata,

Odpowiedzi:

9

Możesz szukać terminu „dwuczęściowy” lub „partycja wierzchołków” lub „kolorowanie” zamiast „wyciąć”. Rozważano różne uogólnienia liczby chromatycznej wzdłuż linii, na które sugerujesz, od połowy lat 80. (lub być może wcześniej). Istnieje kilka wczesnych, trudnych do znalezienia referencji na kanadyjskich konferencjach poświęconych kombinatoryce, ale możesz chcieć sprawdzić Cowen, Goddard i Jesurum (JGT lub SODA 1997) i powiązane referencje / cytowania.

Edytowano 15/02/2011

Jak zauważyli Aravind i Moron (w komentarzach poniżej), następujące odniesienia wskazują, że problem cięcia bez jest trudny do usunięcia z NP, z wyjątkiem trywialnych przypadków.H.

D. Achlioptas. Złożoność kolorów wolnych od Dyskretna matematyka. 165/166 (1997) 21-30. [pdf] .sol

A. Farrugia. Podział wierzchołków na ustalone właściwości dziedziczne indukowane przez dodatek jest trudny do NP. Elektron. J. Combin. 11 (2004) # R46 (9 s.).

RJK
źródło
1
@ Moron: Właściwie odpowiedź na pytanie o partycję bez H jest o wiele ważniejsza niż moja odpowiedź! cstheory.stackexchange.com/questions/884/h-free-partition/…
RJK
Spojrzałem na to i wydawało się, że chodzi o klasy grafów, które zawierają subgrafy itp. Problem ten dotyczy chudości konkretnego wykresu.
Aryabhata
@ Moron: Papier Farrugia obejmuje przypadki, w których każda część jest indukowana addytywnie, tj. Zamknięta w rozłącznym połączeniu i usunięciu wierzchołka. H-freeness jest właściwością indukowaną addytywnością.
RJK
1
Masz rację. Po prostu działałem według streszczenia. W rzeczywistości papierowy users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf ma również znaczenie dla zadanego pytania! Czy masz coś przeciwko, jeśli zmienię twoją odpowiedź, aby dodać te linki?
Aryabhata
1
Drugi artykuł pdf jest tutaj: www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf
Aryabhata
2

Zdaję sobie sprawę, że to może nie odpowiedzieć bezpośrednio na twoje pytanie (dotyczące referencji), ale chciałbym nakreślić możliwe podejście do pokazania twardości NP bez warunku 2-połączonego. Istnieją dwie rzeczy, których brakuje: jedna jest dowodem twardości NP „problemu źródłowego”, że tak powiem, a druga to, że redukuję się do „kolorowej” wersji H-cut, która może lub może nie być przydatne. Jeśli chodzi o pierwsze wąskie gardło, uważam, że mam dowód na to, że jestem leniwy w kwestii formalizacji, więc mam nadzieję, że wkrótce do tego dojdę. Pomyślałem jednak o zmniejszeniu wersji kolorowej do tej, którą prezentujesz, jednak jak dotąd przy odrobinie szczęścia. Jestem również bardzo ciekawy twojego dowodu w przypadku, gdy H jest podłączony 2, czy mógłbyś podać jakieś szczegóły?

Kolorowa wersja jest więc następująca: każdy wierzchołek na wykresie jest wyposażony w listę kolorów z palety P (ustalony, skończony zestaw). Musimy znaleźć wycięcie, aby żadna partycja nie wywoływała monochromatycznej kopii H, co oznacza, że ​​nie ma podzbioru | H | wierzchołki, które wywołują kopię H, a odpowiednia lista kolorów ma niepuste przecięcie.

Oto redukcja z ograniczonego wariantu d-SAT, gdzie d oznacza | H |. (Zauważ, że to oczywiście nie zadziałałoby, gdy d = 2).

Ograniczony wariant d-SAT jest następujący:

  1. Każda klauzula ma albo tylko pozytywne, albo tylko negatywne literały, pozwólcie, że odniosę się do takich klauzul, jak odpowiednio P-klauzule i N-klauzule,

  2. Każda klauzula P może być sparowana z klauzulą ​​N, tak że dwie klauzule dotyczą tego samego zestawu zmiennych.

(Mam pojęcie o tym, dlaczego ta pozornie ograniczona wersja może być trudna - bardzo ściśle powiązane ograniczenie jest trudne i mogę sobie wyobrazić redukcję, chociaż łatwo się myliłem!)

Biorąc pod uwagę ten problem, redukcja może się sugerować. Wykres ma wierzchołek dla każdej zmiennej formuły. Dla każdej klauzuli C_i wywołaj kopię H na zbiorze zmiennych uczestniczących w klauzuli i dodaj kolor i do tego zestawu wierzchołków. To kończy budowę.

Każde zadanie w naturalny sposób odpowiada cięciu:

L = zestaw wszystkich zmiennych, które zostały ustawione na 0, R = zestaw wszystkich zmiennych, które zostały ustawione na 1.

Twierdzenie jest takie, że zadowalające przypisanie odpowiada cięciu monochromatycznemu bez H.

Innymi słowy, (L, R), jeśli otrzyma zadowalające przypisanie, byłby taki, że ani L ani R nie wywołałyby monochromatycznej kopii H. Jeśli L ma taką kopię, to zauważ, że odpowiednia klauzula P musiała mieć wszystkie zmienne ustawione na 0, co przeczy temu, że przypisanie było satysfakcjonujące. I odwrotnie, jeśli R ma taką kopię, to odpowiednia klauzula N musiała mieć wszystkie zmienne ustawione na 1, znowu sprzeczność.

Odwrotnie, rozważ dowolne cięcie i ustaw zmienne z jednej strony na 1, a z drugiej na 0 (zauważ, że nie ma znaczenia, w jaki sposób to robisz - biorąc pod uwagę rodzaj formuły, z którą pracujemy, przypisanie i odwrócenie wersja jest równoważna pod względem satysfakcji). Jeśli to zadanie nie spełnia klauzuli, możemy prześledzić go z powrotem do monochromatycznej kopii H na jednej ze stron, co jest sprzeczne z monochromatyczną H-płynnością cięcia.

Powodem, dla którego należy pozwolić na kolorowanie, jest to, że kopie H mogą ingerować w tworzenie fałszywych kopii H, które nie odpowiadają klauzulom, w bezpośredniej próbie zmniejszenia. Rzeczywiście, zawodzi - źle - nawet gdy H jest czymś tak prostym jak ścieżka.

Nie miałem szczęścia pozbyć się kolorów i nie jestem pewien, czy upraszczam ten problem. Mam jednak nadzieję, że - jeśli jest poprawny - może to być początek.

Neeldhara
źródło
Dziękuję za Twoją odpowiedź. Co do dowodu, który miałem, zacząłem od nie wszystkich równych 3 sat, które zostały przekształcone w wyrażenie o pewnej strukturze, a następnie zbudowałem kilka skomplikowanych (opisujących i rysujących) gadżetów wykorzystujących tę strukturę. Jeśli mam czas, mógłbym gdzieś napisać i odłożyć artykuł (i zamieścić link).
Aryabhata,
Ach, okej Próbowałem zacząć od nie-jeden-w-3-sat, ale bez większego szczęścia (nie wiem, dlaczego nawet spodziewałem się, że zadziała). Chciałbym spojrzeć na szczegóły, jeśli / kiedy je masz, brzmi jak dobra robota! Mam zamiar zatrzymać się na trochę dłużej, FWIW.
Neeldhara,
To była monotoniczna wersja nae-3sat. Dzięki za zachętę! Cieszę się, że wzbudziło twoje zainteresowanie :-)
Aryabhata,
RJK wskazał mi odpowiedź, która prowadzi do artykułu z tym odniesieniem: users.soe.ucsc.edu/~optas/papers/G-free-complex.pdf
Aryabhata