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 w i j n × $n$$n$$w_{ij}$$n \times n$

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 ,{ I $\{ O_i \; | \; i=1 \dots n \}$n × n w i j ≥ 0 O i I j i , j = 1 … n β e i i j = 1 … $\{ 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_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta$$

gdzie pokazuje kolor krawędzi .e i $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 :n n ( n - 1 ) W I j ≥ 0 I J C ( i j ), i j T ⊆ E β e I J ∈ $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$

c(ij)≠c(ik

$$\frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta.$$ oraz $$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 .O ( | T | ! $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 + ∑ c ( k l ) = c ( i j ) , k l ≠ i j w k j$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. T $w_{ij}$$T$$\beta$

Aktualizacja 2:

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

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 i w i i = 1 i ≠ j i j w i j = w j i = 1 w i j = w j i = 0 β = $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 .R R C R $\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 kolorystycej C R i j w j $i$$j$$\mathcal{C}$$\mathcal{R}$$i$$j$$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ XC$\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}$

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 .D = $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.N $k$$NP$

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