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ę G , k , wiemy, że ¯ G może być n - k + 1 -kolorowane zk wierzchołkami, wszystkie kolorowe True iff G mają k- klikę. Nazywamy oryginalne wierzchołki G v 1 , … , v n, a następnie dodajemy do ¯ G dodatkowe wierzchołki: C i j z 1 ≤ i ≤ n , 0 ≤ j ≤ $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 C i j może mieć kolor True, jeśli tylko między wierzchołkami { v 1 , … , v i } znajdują się co najmniej j wierzchołki w kolorze True. Tak więc, każde C i 0 może być Prawdą. Następnie C i j dla j > 0 otrzymuje kolor C ( i - 1 ) j ∨ C ( i - 1 ) ( j - 1 )$C_{ij}$$\{v_1,\ldots, v_i\}$$j$$C_{i0}$$C_{ij}$$j > 0$ v I gdzie wszystkie kolory spoza prawdziwe są traktowane jako FAŁSZ Jest. K -clique w$C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$$k$$G$iff C n k można barwić prawda, jeśli więc siła, którą zabarwienie nowy wykres jest colorable IFF byłok-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żą K n - k + 1 w naszym wykresie, wybrać wierzchołki T, F i ziemię, a następnie połączyć wszystkie inni do wszystkiego, ale V i s; zapewnia to, że C i j i inne gadżety otrzymają tylko 3 kolory.$K_{n-k+1}$$v_i$$C_{ij}$

W każdym razie część ¯ G 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.

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

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

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

(3) Dla każdego potrójnego { x , y , z } wierzchołków w H , gdzie y = ( v , i ) i z = ( u , j ) , sprawdź, czy spełniony jest jeden z następujących warunków: albo u ≠ v i i = j lub u i v to nieprzylegające wierzchołki w G o max ( i , j ) ≤ $\{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ą n -clique do H . W obrębie tej kliki wybierz trzy wierzchołki x ′ , y ′ i z ′ . Połącz x z każdym wierzchołkiem kliki oprócz y ′ i z ′ ; połącz y z każdym wierzchołkiem kliki oprócz x ′ i z ′ ; i połącz z z każdym wierzchołkiem kliki oprócz x ′ i y ′ .$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 x , y i z od wszystkich z nich otrzymuje się taki sam kolor jak drugi obowiązującą barwienia H . Klikę w G można odzyskać po zabarwieniu H jako zbiór wierzchołków ( v , i ), które mają tę samą klasę kolorów co x i mają i ≤ k .$x$$y$$z$$H$$G$$H$$(v,i)$$x$$i\le k$

?? 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