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.