NP-Completitud de un problema de coloración gráfica

Formulación Alternativa

Se me ocurrió una formulación alternativa para el siguiente problema. La formulación alternativa es en realidad un caso especial del problema a continuación y utiliza gráficos bipartitos para describir el problema. Sin embargo, creo que la formulación alternativa sigue siendo NP-hard. La formulación alternativa utiliza un conjunto disjunto de nodos entrantes y salientes que simplifica la definición del problema.

Dados nodos salientes y entrantes (los nodos rojo y azul en la figura respectivamente), y un conjunto 's de tamaño n \ veces n de pesos de borde entre los vértices salientes y entrantes. El objetivo del problema es colorear los bordes gruesos de la figura para que para cada nodo entrante, se cumpla una condición.n w i j n × $n$$n$$w_{ij}$$n \times n$

Dado un conjunto de vértices de salida, un conjunto de vértices de entrada, pesos entre 's e ' s para , y una constante positiva , encuentre el número mínimo de colores para los bordes (bordes gruesos en la figura anterior) de modo que para todos ,{ 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$$

donde muestra el color del borde .$c(i)$$e_{ii}$

Antigua formulación

El siguiente problema me parece NP-duro, pero no pude mostrarlo. Cualquier prueba / comentario para mostrar la dureza o facilidad de la misma es apreciada.

Suponga que es un gráfico dirigido ponderado completo con nodos y bordes. Deje que muestre el peso del borde y muestre el color del borde . Dado un subconjunto de los bordes y una constante positiva el objetivo es: encontrar el número mínimo de colores de manera que para cada :n n ( n - 1 ) w i j ≥ 0 i j c ( i j ) i j T ⊆ $K_n=\langle V,E \rangle$$n$$n(n-1)$$w_{ij} \ge 0$$ij$$c(ij)$$ij$$T \subseteq E$e i j ∈ $\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.$$ y $$c(ij) \neq c(ik) \quad for \quad j \neq k$$

Tenga en cuenta que en el problema anterior, solo los bordes en deben colorearse. Ese es el problema que se puede resolver en .O ( | T | ! $T$$\mathcal{O}(|T|!)$

Actualizar:

Después del comentario de Tsuyoshi Ito, actualicé el problema. El denominador se cambia de a . Por lo tanto, el denominador contiene los pesos fuera de también. Es por eso que mencioné el gráfico completo en la definición. 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$

También agregué una restricción adicional . Eso significa que los bordes salientes de un nodo deben ser de diferentes colores (pero los colores entrantes pueden ser los mismos siempre que se mantenga la desigualdad). Esto pone un intuitivo límite inferior en el número de colores, que es el grado fuera máximo de los nodos en .$c(ij) \neq c(ik) \quad for \quad j \neq k$$T$

Como mencionó Tsuyoshi, 's, y son entradas al problema y los colores de borde son la salida.$w_{ij}$$T$$\beta$

Actualización 2:

El problema no impone que los bordes y sean del mismo color. e j $e_{ij}$$e_{ji}$

Es bastante simple demostrar que la formulación alternativa es NP-hard. La reducción es del problema de coloración del vértice. Dado un gráfico G con vértices, creamos una instancia del problema anterior con vértices de salida y vértices de entrada. Los pesos se establecen de la siguiente manera: para todo , dejemos . Para , si hay un borde entre el vértice y el vértice , deje , de lo contrario deje . Además, let .n n i w i i = 1 i ≠ j i j w i j = w j i = $n$$n$$n$$i$$w_{ii}=1$$i \neq j$$i$$j$$w_{ij}=w_{ji}=1$β = $w_{ij}=w_{ji}=0$$\beta=1$

Esto es bastante obvio pero difícil de describir por qué la reducción es correcta. Deje que muestre la instancia del color del gráfico y muestre la instancia reducida del problema. Para mostrar que la reducción anterior da una solución correcta, debemos mostrar que (1) cada coloración válida para es válida para . (2) la respuesta dada por es mínima para .R $\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$

Si y son dos vértices adyacentes de , entonces deben tener diferentes colores en . Esto se debe a que si y son adyacentes y tienen el mismo color, la fracción daría como resultado , donde tiene un valor positivo. Por lo tanto, la condición no se cumple. Además, cada coloración válida (pero no necesariamente mínima) para , es una coloración válida para también. De ello se desprende que en una coloración válida de$i$$j$R i j w j $\mathcal{C}$$\mathcal{R}$$i$$j$$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ XCRCRCRRC$\frac{1}{1+X}$$X$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$, cada par de nodos adyacentes tienen colores diferentes, por lo que la condición se cumple para todos los bordes coloreados de en la solución. Dado que cada coloración de es una coloración válida para , la solución mínima para debe ser una solución mínima para . De lo contrario, no es mínimo porque la solución a da una solución con un número menor de colores.$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{C}$

EDITAR : La construcción a continuación no funciona del todo, según el comentario de Tsuyoshi Ito a continuación, no impone que . Sin embargo, lo dejo en caso de que sea un comienzo útil. Además, no debe incluir arcos con peso .T $c(ij)=c(ji)$$T$$0$

A lo largo de las líneas sugeridas por Mohsen, comience con Edge Coloring, convierta el gráfico a un dígrafo en el mismo conjunto de vértices donde tenemos y en , dé a todos los arcos (en este punto) peso , luego agregue y a con , set a y .D = ( V , A ) ∀ u v ∈ E ( u , v ) ( v , u ) A a ∈ A w a = 1 ∀ x y ∉ E ( x , y ) ( y , x ) A w x y = w y x$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$β 1 T = $w_{xy}=w_{yx}=0$$\beta$$1$$T=A$

Entonces, la condición solo se cumple si no hay dos arcos incidentes en el mismo vértice que tengan el mismo color, sin tener en cuenta los arcos que provienen de no bordes en el gráfico original (ya que tienen un peso ). Esta coloración se puede convertir nuevamente en una coloración adecuada para el gráfico original.$0$

Técnicamente, he convertido su problema original en un problema de decisión ("¿es el gráfico coloreable con colores?"), Pero de todos modos esto debía hacerse para encajar en y es efectivamente intercambiable hasta un polinomio.N $k$$NP$

Entonces, creo que funciona, ¿o acabo de mostrar que algo más es duro? ;)$NP$