NP-Kompletność problemu kolorowania wykresu

Alternatywne sformułowanie

Wymyśliłem alternatywne sformułowanie do poniższego problemu. Alternatywne sformułowanie jest w rzeczywistości szczególnym przypadkiem poniżej problemu i wykorzystuje dwuczęściowe wykresy do opisania problemu. Uważam jednak, że alternatywny preparat jest nadal trudny do NP. Alternatywne sformułowanie wykorzystuje rozłączny zestaw przychodzących i wychodzących węzłów, co upraszcza definicję problemu.

Biorąc pod uwagę węzłów wychodzących i węzłów przychodzących (odpowiednio czerwony i niebieski węzeł na rysunku) oraz zbiór wielkości wag krawędzi między wierzchołkami wychodzącymi i przychodzącymi. Problem polega na pokolorowaniu grubych krawędzi na rysunku, tak aby dla każdego przychodzącego węzła obowiązywał warunek. $n$ $n$ $w_{ij}$ $n \times n$

Dwustronny wykres problemu

Biorąc pod uwagę zestaw wierzchołków wyjściowych, zbiór wierzchołków wejściowych, wagi między a dla , a dodatnia stała , znajdź minimalna liczba kolorów krawędzi (grube krawędzie na powyższym rysunku), tak że dla wszystkich , $\{ O_i \; | \; i=1 \dots n \}$ $\{ I_i\; | \; i=1 \dots n \}$ $n \times n$ $w_{ij} \ge 0$ $O_i$ $I_j$ $i,j=1 \dots n$ $\beta$ $e_{ii}$ $j=1 \dots n$

$\frac{w_{j j}}{1 + \sum_{c (i) = c (j), i \neq j} w_{i j}} \geq β$ $\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta$
gdzie pokazuje kolor krawędzi . $c(i)$ $e_{ii}$

Stare sformułowanie

Poniższy problem wydaje mi się trudny do rozwiązania, ale nie mogłem go pokazać. Doceniamy każdy dowód / komentarz wskazujący na jego twardość lub łatwość.

Załóżmy, że jest pełnym ważonym, ukierunkowanym wykresem z węzłami i krawędziami. Niech pokaże wagę krawędzi a pokazuje kolor krawędzi . Biorąc pod uwagę podzbiór krawędzi i stałą dodatnią celem jest: znaleźć minimalną liczbę kolorów, tak aby dla każdego : $K_n=\langle V,E \rangle$ $n$ $n(n-1)$ $w_{ij} \ge 0$ $ij$ $c(ij)$ $ij$ $T \subseteq E$ $\beta$ $e_{ij} \in T$

$\frac{w_{i j}}{1 + \sum_{c (k l) = c (i j), k l \neq i j} w_{k j}} \geq β .$ $\frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta.$ oraz $c (i j) \neq c (i k) f o r j \neq k$ $c(ij) \neq c(ik) \quad for \quad j \neq k$

Należy pamiętać, że w powyższym problemie tylko krawędzie w muszą być pokolorowane. To jest problem, który można rozwiązać w . $T$ $\mathcal{O}(|T|!)$

Aktualizacja:

Po komentarzu Tsuyoshi Ito zaktualizowałem problem. Mianownik zmienia się z na . Dlatego mianownik zawiera ciężary poza , jak również. Właśnie dlatego wspomniałem pełny wykres w definicji. $1+\sum_{c(kj)=c(ij),k \neq i,e_{kj} \in T} w_{kj}$ $1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}$ $T$

Dodałem również dodatkowe ograniczenie . Oznacza to, że krawędzie wychodzące z węzła muszą mieć różne kolory (ale kolory przychodzące mogą być takie same, o ile utrzymuje się nierówność). Intuicyjny Stawia dolną granicę ilości kolorów, czyli stopień poza maksymalnie węzłów . $c(ij) \neq c(ik) \quad for \quad j \neq k$ $T$

Jak wspomniał Tsuyoshi, , i stanowią dane wejściowe do problemu, a kolory krawędzi - dane wyjściowe. $w_{ij}$ $T$ $\beta$

Aktualizacja 2:

Problem nie wymusza na krawędziach i być tego samego koloru. $e_{ij}$ $e_{ji}$

— Hel
źródło

@Raphael: Zwykle problem kolorowania krawędzi wydaje się dobrym kandydatem do redukcji. Znalezienie najprostszego np. Trudnego problemu dla redukcji jest najtrudniejszą częścią. Następnym krokiem jest znalezienie odpowiednich wag dla mapowania. Myślę, że jeśli problem kolorowania krawędzi zostanie zredukowany do powyższego problemu, wagi powinny być albo 0/1, albo musimy rozwiązać system nierówności, aby znaleźć wagi.

— Hel

Kilka uwag na temat sformułowania problemu: (1) Jaki jest wkład? Wydaje mi się, że dane wejściowe to w_ij dla wszystkich krawędzi, T i β, ale jeśli tak, nie powinieneś definiować w_ij i c (ij) tak, jakby były podane w ten sam sposób. (2) Jak rozumiem, co napisałeś, krawędzie poza T nigdy nie są wymienione. Dlatego łatwiej jest zdefiniować ukierunkowany wykres składający się z krawędzi w T zamiast uwzględnienia pełnego ukierunkowanego wykresu.

— Tsuyoshi Ito

@TsuyoshiIto: Dziękuję za komentarze, zaktualizowałem pytanie.

— Hel

Nawiasem mówiąc, problem wydaje mi się dość niechlujny. Jeśli wyjaśnisz, w jaki sposób osiągnąłeś ten problem (innymi słowy, dlaczego jesteś zainteresowany tym problemem), może to pomóc innym zrozumieć problem.

— Tsuyoshi Ito

@TsuyoshiIto: 1) Problem jest szczególnym przypadkiem planowania w bezprzewodowych sieciach ad-hoc. odnosi się do zestawu transmisji, a wagi reprezentują współczynniki tłumienia sygnału. Ograniczenie pięści odnosi się również do stosunku sygnału do zakłóceń plus szum. 2) „mianownik zawiera tylko masy krawędzi w T” jest teraz usuwany.

T

$T$

— Hel

Odpowiedzi:

Dość łatwo jest wykazać, że alternatywny preparat jest twardy NP. Redukcja wynika z problemu zabarwienia wierzchołków. Biorąc pod uwagę wykres G z wierzchołkami, tworzymy przykład powyższego problemu z wierzchołkami wyjściowymi i wierzchołkami wejściowymi. Wagi ustawia się w następujący sposób: dla wszystkich , niech . W przypadku , jeśli istnieje krawędź między wierzchołkiem a wierzchołkiem , niech , w przeciwnym razie niech . Ponadto niech . $n$ $n$ $n$ $i$ $w_{ii}=1$ $i \neq j$ $i$ $j$ $w_{ij}=w_{ji}=1$ $w_{ij}=w_{ji}=0$ $\beta=1$

Jest to dość oczywiste, ale trudne do opisania, dlaczego redukcja jest poprawna. Niech pokaże wystąpienie kolorowania wykresu, a pokaże zredukowane wystąpienie problemu. Aby pokazać powyższą redukcję, daje prawidłowe rozwiązanie, musimy pokazać, że (1) każda poprawna kolorystyka dla jest również ważna dla . (2) odpowiedź udzielona przez jest minimalna dla . $\mathcal{C}$ $\mathcal{R}$ $\mathcal{R}$ $\mathcal{C}$ $\mathcal{R}$ $\mathcal{C}$

Jeśli i są dwoma sąsiadującymi wierzchołkami , to muszą mieć różne kolory w . Jest tak, ponieważ jeśli i są sąsiadujące i mają ten sam kolor, ułamek spowoduje, że , gdzie ma wartość dodatnią. Dlatego warunek nie obowiązuje. Ponadto każda poprawna (ale niekoniecznie minimalna) kolorystyka dla , jest również poprawna dla . Wynika to z faktu, że w prawidłowej kolorystyce $i$ $j$ $\mathcal{C}$ $\mathcal{R}$ $i$ $j$ $\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ $\frac{1}{1+X}$ $X$ $\mathcal{C}$ $\mathcal{R}$ $\mathcal{C}$ , każda para sąsiednich węzłów ma różne kolory, więc warunek obowiązuje dla wszystkich kolorowych krawędzi w rozwiązaniu. Ponieważ każda kolorystyka jest poprawną kolorystyką dla , minimalne rozwiązanie dla musi być również minimalnym rozwiązaniem dla . W przeciwnym razie nie jest to minimalne, ponieważ rozwiązanie daje rozwiązanie o mniejszej liczbie kolorów. $\mathcal{R}$ $\mathcal{C}$ $\mathcal{R}$ $\mathcal{R}$ $\mathcal{C}$ $\mathcal{C}$

— Hel
źródło

EDYCJA : Poniższa konstrukcja nie do końca działa, zgodnie z poniższym komentarzem Tsuyoshi Ito, nie wymusza tego . Zostawiam to na wypadek, gdyby był to użyteczny początek. Ponadto nie powinien obejmować łuków o wadze . $c(ij)=c(ji)$ $T$ $0$

Wzdłuż linii sugerowanych przez Mohsena, zacznij od Edge Coloring, przekonwertuj wykres na wykrój na tym samym zestawie wierzchołków, gdzie mamy i w , nadaj wszystkim łukom (w tym momencie) wagę , a następnie dodaj i do z , a zestaw do i . $G=(V,E)$ $D=(V,A)$ $\forall uv\in E$ $(u,v)$ $(v,u)$ $A$ $a \in A$ $w_{a} = 1$ $\forall xy \notin E$ $(x,y)$ $(y,x)$ $A$ $w_{xy}=w_{yx}=0$ $\beta$ $1$ $T=A$

Wtedy warunek jest spełniony tylko wtedy, gdy żadne dwa łuki padające na ten sam wierzchołek nie mają tego samego koloru, z pominięciem łuków pochodzących z innych niż krawędzie oryginalnego wykresu (ponieważ mają wagę ). Tę kolorystykę można następnie przekształcić z powrotem w odpowiednią kolorystykę dla oryginalnego wykresu. $0$

Technicznie przekształciłem twój pierwotny problem w problem decyzyjny („czy wykres można pokolorować za pomocą kolorów?”), Ale i tak należało to zrobić, aby dopasować się do i można go skutecznie zamieniać na wielomian. $k$ $NP$

Więc myślę, że to działa, czy też właśnie pokazałem coś innego, by być twardym? ;) $NP$

— Luke Mathieson
źródło

Jak wymusić to c (ij) = c (ji)? Nie jest to prawdą w przypadku omawianego problemu, jeśli dobrze go rozumiem.

— Tsuyoshi Ito

Słuszna uwaga. Zredaguję oryginalny post, aby zanotować problem.

— Luke Mathieson