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)?
Odpowiedzi:
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.).
źródło
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:
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,
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.
źródło