NP-Completude de um problema de coloração de gráfico

Formulação Alternativa

Eu vim com uma formulação alternativa para o problema abaixo. A formulação alternativa é realmente um caso especial do problema abaixo e usa gráficos bipartidos para descrever o problema. No entanto, acredito que a formulação alternativa ainda é NP-difícil. A formulação alternativa usa um conjunto separado de nós de entrada e saída que simplifica a definição do problema.

Dado nós de saída e n de entrada (os nós vermelho e azul na figura, respectivamente) e um conjunto w i j 's de tamanho n × n de pesos de borda entre os vértices de saída e de entrada. O objetivo do problema é colorir as arestas grossas da figura para que, para cada nó recebido, uma condição seja mantida.$n$$n$$w_{ij}$$n \times n$

Dado um conjunto de vértices de saída, um conjunto { I $\{ O_i \; | \; i=1 \dots n \}$ de vértices de entrada, n x n pesos w i j ≥ 0 entre O i 's e eu j ' s para i , j = 1 ... n , e uma constante positiva β , encontrar o número mínimo de cores para as arestas e i i (arestas grossas na figura acima), de modo que, para todos os j = 1 … 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_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}} \ge \beta$$

onde mostra a cor da aresta e i i .$c(i)$$e_{ii}$

Formulação antiga

O seguinte problema parece difícil para mim, mas não consegui mostrar. Qualquer prova / comentário para mostrar a dureza ou facilidade é apreciada.

Suponha é um gráfico ponderada completo dirigido com n nodos e n ( n - 1 ) arestas. Deixe w i j ≥ 0 mostrar o peso da aresta i j e c ( i j ) mostre a cor da aresta i j . Dado um subconjunto das arestas T ⊆ E e uma constante positiva β, o objetivo é: encontrar o número mínimo de cores para que cada$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$

e c(ij)≠c(ik

$$\frac{w_{ij}}{1+\sum_{c(kl)=c(ij),kl \neq ij} w_{kj}} \ge \beta.$$ $$c(ij) \neq c(ik) \quad for \quad j \neq k$$

Observe que no problema acima, apenas as arestas em precisam ser coloridas. Esse é o problema que pode ser resolvido em O ( | T | ! ) .$T$$\mathcal{O}(|T|!)$

Atualizar:

Após o comentário de Tsuyoshi Ito, atualizei o problema. O denominador é alterado de para 1 + ∑ c ( k l ) = c ( i j ) , k l ≠ i j w k $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}$. Portanto, o denominador contém os pesos exteriores bem. Foi por isso que mencionei o gráfico completo na definição.$T$

Também adicionei uma restrição adicional . Isso significa que as arestas de saída de um nó devem ter cores diferentes (mas as cores recebidas podem ser as mesmas desde que a desigualdade se mantenha). Isso coloca um intuitivo limite inferior no número de cores, que é o grau out-máxima dos nós no T .$c(ij) \neq c(ik) \quad for \quad j \neq k$$T$

$w_{ij}$$T$$\beta$

Atualização 2:

$e_{ij}$$e_{ji}$

$n$$n$$n$$i$$w_{ii}=1$$i \neq j$$i$$j$$w_{ij}=w_{ji}=1$$w_{ij}=w_{ji}=0$$\beta=1$

$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$

$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}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{C}$ fornece uma solução com um número menor de cores.

$c(ij)=c(ji)$$T$$0$

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

$0$

$k$$NP$

$NP$