Naturalna redukcja CLIQUE do k-Color

Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym wyjaśnić przyjacielowi dość krótko, bez potrzeby opisywania języka pośredniego, takiego jak SAT.

Jako przykład tego, czego szukam, oto bezpośrednia redukcja w odwrotnym kierunku: Biorąc pod uwagę G z $n$ i trochę $k$ (liczba kolorów), utwórz wykres G 'z $kn$ wierzchołkami (jeden na kolor na wierzchołek) . Wierzchołki $v'$ , $u'$ odpowiadające odpowiednio wierzchołkom $v, u$ i kolorom $c, d$ sąsiadują, wtedy i tylko wtedy, gdy $v \neq u$ i ( $c \neq d$ lub $vu \not \in G$ ). $n$ -clique w $G'$ jest tylko jednym wierzchołkiem za wierzchołkiem w $G$ i odpowiednie kolory są właściwe $k$ -coloring z $G$ . Podobnie, każde prawidłowe $k$ kolorowanie $G$ ma odpowiednią klikę w $G'$ .

Edycja : Aby dodać krótką motywację, pierwotne 21 problemów Karpa zostało potwierdzonych jako NP-Complete przez drzewo redukcji, w których CLIQUE i liczba chromatyczna tworzą korzenie głównych poddrzewa. Istnieją pewne naturalne redukcje między problemami w poddrzewie CLIQUE i poddrzewie Liczby Chromatycznej, ale wiele z nich jest tak samo trudnych do znalezienia, jak ten, o który pytam. Staram się zbadać, czy struktura tego drzewa wykazuje strukturę leżącą u podstaw innych problemów, czy też jest to całkowicie konsekwencja tego, które redukcje zostały znalezione jako pierwsze, ponieważ motywacja do poszukiwania redukcji między dwoma problemami jest mniejsza wiadomo, że należą do tej samej klasy złożoności. Z pewnością porządek miał pewien wpływ, a części drzewa można zmienić, ale czy można je dowolnie zmienić?

Edycja 2 : Nadal szukam bezpośredniej redukcji, ale oto szkic najbliższego, jaki dostałem (powinna to być poprawna redukcja, ale ma CIRCUIT SAT jako wyraźnego pośrednika; jest to nieco subiektywne, czy jest to lepsze niż składające się z dwóch redukcji, o których mowa w akapicie pierwszym).

Biorąc pod uwagę , wiemy, że może być -kolorowane wierzchołkami, wszystkie kolorowe True iff mają klikę. Nazywamy oryginalne wierzchołki a następnie dodajemy do dodatkowe wierzchołki: z , $G, k$ $\overline{G}$ $n-k+1$ $k$ $G$ $k$ $G$ $v_1, \ldots, v_n$ $\overline G$ $C_{ij}$ $1 \le i \le n$ $0 \le j \le k$ . Kluczowym niezmiennikiem będzie to, że może mieć kolor True, jeśli tylko między wierzchołkami znajdują się co najmniej wierzchołki w kolorze True. Tak więc, każde może być Prawdą. Następnie dla otrzymuje kolor $C_{ij}$ $\{v_1,\ldots, v_i\}$ $j$ $C_{i0}$ $C_{ij}$ $j > 0$ gdzie wszystkie kolory spoza prawdziwe są traktowane jako FAŁSZ Jest. -clique w $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ $k$ $G$ iff można barwić prawda, jeśli więc siła, którą zabarwienie nowy wykres jest colorable IFF było-clique w pierwotnym wykresie. $C_{nk}$ $k$

AND i OR gadżety egzekwować relacje są bardzo podobnie do redukcji z obwodu SAT do 3-kolorowy, ale tutaj należą w naszym wykresie, wybrać wierzchołki T, F i ziemię, a następnie połączyć wszystkie inni do wszystkiego, ale s; zapewnia to, że i inne gadżety otrzymają tylko 3 kolory. $K_{n-k+1}$ $v_i$ $C_{ij}$

W każdym razie część tej redukcji wydaje się bezpośrednia, ale użycie bramek AND / OR jest znacznie mniej bezpośrednie. Pozostaje pytanie, czy istnieje bardziej elegancka obniżka? $\overline G$

Edycja 3 : Pojawiło się kilka komentarzy na temat tego, dlaczego trudno byłoby znaleźć tę redukcję. CLIQUE i k-Color to rzeczywiście zupełnie inne problemy. Jednak nawet bez redukcji odpowiedź, która wyjaśnia, dlaczego redukcja jest trudna w jednym kierunku, ale możliwa w drugim, byłaby bardzo pomocna i przyczynia się w dużym stopniu do problemu.

— William Macrae
źródło

Rodzaj bezpośredniej redukcji, którego szukasz, może być trudny do znalezienia, ponieważ Klika i kolorystyka są swego rodzaju przeciwieństwem w tym sensie, że klika 1 jest tak łatwa do znalezienia jak n-kolorowanie. Może więc redukcja powinna mieć postać:

ma kolor

wtedy i tylko wtedy, gdy

ma klikę

G′ $G'$

n−k $n-k$

G $G$

k $k$

— Martin Vatshelle

Zgadzam się, że to trudne; to jest powód mojego zainteresowania; W pytaniu przedstawię szczegółowo motywację.

-coloring pomysł nie dostał mi najbliższa. Jeśli w

jest

klika, wówczas

może mieć wszystkie wierzchołki w klice monochromatyczne, ponieważ są one niezależnym zestawem. Problem polega na tym, że liczba chromatyczna reszty może się różnić. Połączenie dwóch wierzchołków z

zmusza je do tego samego koloru, ale nie mam pojęcia, który zestaw wierzchołków ma wymusić. Gadżet, że niektóre siły

n−k $n-k$

k $k$

G $G$

G¯¯¯¯ $\overline{G}$

Kn−k−1 $K_{n-k-1}$

i $i$

j $j$ wierzchołki być monochromatyczny by to zrobić.

— William Macrae,

Zgadzam się z Martinem, że może to nawet nie być wykonalne (bez przejścia, powiedzmy 3SAT). Klika i kolorystyka mają ze sobą niewiele wspólnego. Chcę zatem przypomnieć twierdzenie Erdősa, biorąc pod uwagę naturals g i k, istnieje wykres z obwodem co najmniej g i liczbą chromatyczną co najmniej k (pomyśl o tym przez chwilę, jeśli go nie znasz). Na koniec, twoja redukcja musi być również świadoma, że chociaż Clique (i Independent Set) jest w

sparametryzowany przez zestaw roztworów, nie ma równoważnej parametryzacji dla liczby chromatycznej wykresu. W[1] $W[1]$

— Pål GD

Nie rozumiem komentarza @ MartinVatshelle. O ile mi wiadomo, wszystkie 1-klika, 1-kolorowanie, n-klika i n-kolorowanie są banalne na tym samym poziomie. (nie sądzę, że zawsze możesz odpowiedzieć na 1-klikową odpowiedź TAK: wykres wejściowy może być pusty!)

— Yixin Cao,

Myślę, że punkt Martina jest jego pokaz

, ale trudniej znaleźć

niż

. W tych dwóch koncepcjach jest więc trochę dualizmu. Punkt PålGD na temat twierdzenia Erdősa jest świetny (i uwielbiam to twierdzenie), ponieważ wykresy z dużym obwodem mają dużą liczbę niezależności, a zatem ich odwrócone będą miały duże kliky. Ogólnie wydaje się, że jest tu pułapka, która polega na powiązaniu klików i koloryzacji na tych samych lub podobnych wykresach, ale podobnie jak w odwrotnym kierunku redukcja może stworzyć wykres zupełnie inny niżχ(G)=4 $\chi(G)=4$

χ(G)=3 $\chi(G)=3$

K4 $K_4$

K3 $K_3$

.G $G$

— William Macrae,

Odpowiedzi:

Biorąc pod uwagę wykres a liczba tak, że chcesz wiedzieć, czy zawiera -clique, niech n będzie liczbę wierzchołków w . Konstruujemy kolejny wykres , taki że jest -kolorowalny wtedy i tylko wtedy, gdy ma klikę, w następujący sposób: $G$ $k$ $G$ $k$ $G$ $H$ $H$ $n$ $G$ $k$

(1) Dla każdego wierzchołka w utwórz klikę wierzchołków w , gdzie wynosi od do . $v$ $G$ $n$ $(v,i)$ $H$ $i$ $1$ $n$

(2) po jednym dodatkowym wierzchołków z . $x$ $H$

(3) Dla każdego potrójnego wierzchołków w , gdzie i , sprawdź, czy spełniony jest jeden z następujących warunków: albo i lub i to nieprzylegające wierzchołki w o $\{x,y,z\}$ $H$ $y=(v,i)$ $z=(u,j)$ $u\ne v$ $i=j$ $u$ $v$ $G$ $\max(i,j)\le k$ . Jeśli któryś z tych dwóch rzeczy jest prawdą, dodać kolejną -clique do . W obrębie tej kliki wybierz trzy wierzchołki , i . Połącz z każdym wierzchołkiem kliki oprócz i ; połącz z każdym wierzchołkiem kliki oprócz i ; i połącz z każdym wierzchołkiem kliki oprócz i . $n$ $H$ $x'$ $y'$ $z'$ $x$ $y'$ $z'$ $y$ $x'$ $z'$ $z$ $x'$ $y'$

Gadżety dodaje się w etapie (3) zapobiegają trzykrotność wierzchołków , i od wszystkich z nich otrzymuje się taki sam kolor jak drugi obowiązującą barwienia . Klikę w można odzyskać po zabarwieniu jako zbiór wierzchołków które mają tę samą klasę kolorów co i mają . $x$ $y$ $z$ $H$ $G$ $H$ $(v,i)$ $x$ $i\le k$

— David Eppstein
źródło

To jest cudowne.

— William Macrae

Z jakiegoś powodu moja edycja została odrzucona, ale ostatnie zdanie powinno opisywać wierzchołki G zamiast H (ponieważ ma na celu opisanie kliki w G). Coś w stylu „Kliki w

można odzyskać po zabarwieniu H jako

” Ponadto zapomniałem podziękować za odpowiedź, to było bardzo pomocne! G $G$

{v:∃i≤kχ((v,i))=χ(x)}. $\{v : \exists i \le k \chi((v,i)) = \chi(x) \}.$

— William Macrae

Jasne, możesz dodać kolejną klauzulę do tego zdania na temat zdejmowania

z każdej pary, ale myślałem, że ten krok był wystarczająco łatwy do pominięcia, a moim ogólnym odczuciem jest to, że (kiedy można je wystarczająco krótko) proza jest zwykle bardziej czytelny niż formuła. i $i$

— David Eppstein

Zgadzam się, że proza jest bardziej preferowana. Może po prostu dodanie wyrażenia typu „pierwsza współrzędna każdego (v, i) ...” to pomysł. Powodem mojej troski o technikę jest to, że przy zmniejszaniu w pierwszym czytaniu może być trudno zachować dokładne definicje elementów w pierwszym języku i drugim, i który jest który. Gdy tylko coś wydaje się złamać definicję, może rzucić mnie na pętlę. Gdybym miał problem ze zrozumieniem poprzednich zdań i dotarł do ostatniego, ustaliłbym, że G i H mają wierzchołki formy (v, i).

— William Macrae

I should also say that I think you've done a much better job talking through this reduction than almost any other that I've read. There's a problem in the literature that many reductions are stated formally with no motivation or intuition, and you've avoided that very nicely.

— William Macrae

-7

?? coloring and clique finding have been known to be tightly coupled for decades via graph theory (possibly even in the 60s?) even not through SAT as an intermediary (which became typical after the Cook proof in 1971). believe there are algorithms based on the following basic property:

If G contains a clique of size k, then at least k colors are needed to color that clique; in other words, the chromatic number is at least the clique number: $\chi(G) \ge \omega(G).\,$

not sure of exact refs but [1,2] are good places to start, an exact algorithm or ref is at least likely cited in these books.

[1] Cliques, coloring, & satisfiability, 2nd DIMACS challenge

[2] Dimacs vol 26: Cliques, coloring and satisfiability

— vzn
źródło

Using the property

χ(G)≥ω(G) $\chi(G) \geq \omega(G)$ , you can invoke an algorithm for

k−COLORABILITY $k-COLORABILITY$ on

G $G$ : if the algorithm returns

YES $YES$ , then

G $G$ does not contain any clique of size at least

k+1 $k+1$ . However the opposite implication does not hold: if the algorithm returns

NO $NO$ , then

G $G$ may or may not have a clique of size at least

k+1 $k+1$ (as a counterexample, consider a pyramid whose polygonal base has an odd number of vertices: it is not

3 $3$ -colorable, however it has not any clique of size at least

4 $4$ ).

— Giorgio Camerani

yes, agreed; as I interpret it the original post was not insistent on the direction of the reduction but more emphasized avoiding SAT as the intermediary, asking for a "fairly brief explanation". also conspicuously nobody mentioned the above factoid so far.... the question & comments also seem to inaccurately indicate in various ways the two problems are not tightly coupled....

— vzn

Apologies if the direction was ambiguous. I am interested in a correct reduction (YES

⟺ $\iff$ YES), and I am interested in a reduction from Clique to k-Color. I have the other direction and it is explained in my post. There are certainly many things that relate cliques in graphs to colorings in graphs and vice versa, and indeed I have seen many of them (and I assume many others here have seen many of them), but I'm really interested exclusively in a direct reduction or a convincing explanation of why it might not exist.

— William Macrae

@vzn: My comment was not meant to criticize your answer. Truth be told, initially I made a reasoning similar to yours, but then I realized that, if the opposite implication would have hold, then

3−COLORING $3-COLORING$ on general graphs, which is known to be NP-complete, would have been solvable trivially by just checking whether the input graph had a clique of

4 $4$ nodes: any

G $G$ would have been

3 $3$ -colorable if and only if it does not contain any clique of size

4 $4$ (that's plain false, of course, as the pyramid counterexample shows). By the way: I'm not the one who downvoted.

— Giorgio Camerani

@WilliamMacrae: It was perfectly clear that you wanted a

⟺ $\Longleftrightarrow$ reduction, otherwise it wouldn't have been a reduction! Also, it was perfectly clear that you wanted a reduction from

CLIQUE $CLIQUE$ to

COLORING $COLORING$ and not the other way.

— Giorgio Camerani