NP-exhaustivité d'un problème de coloration de graphe

Formulation alternative

Je suis venu avec une formulation alternative au problème ci-dessous. La formulation alternative est en fait un cas particulier du problème ci-dessous et utilise des graphiques bipartites pour décrire le problème. Cependant, je crois que la formulation alternative est toujours NP-difficile. La formulation alternative utilise un ensemble disjoint de nœuds entrants et sortants qui simplifie la définition du problème.

Soit nœuds sortants et nœuds entrants (les nœuds rouge et bleu sur la figure respectivement), et un ensemble de taille de poids de bord entre les sommets sortants et entrants. Le but du problème est de colorer les bords épais de la figure de sorte que pour chaque nœud entrant, une condition soit respectée.n w i j n × $n$$n$$w_{ij}$$n \times n$

Étant donné un ensemble de sommets de sortie, un ensemble de sommets d'entrée, poids entre et pour , et une constante positive , trouver le nombre minimum de couleurs pour les arêtes (arêtes épaisses sur la figure ci-dessus) telles que pour tout ,{ 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$$

où montre la couleur du bord .e i $c(i)$$e_{ii}$

Ancienne formulation

Le problème suivant me semble NP-difficile, mais je ne pouvais pas le montrer. Toute preuve / commentaire pour en montrer la dureté ou la facilité est apprécié.

Supposons que est un graphe orienté pondéré complet avec nœuds et arêtes. Soit le poids du bord et la couleur du bord . Etant donné un sous-ensemble des arêtes et une constante positive le but est: trouver le nombre minimum de couleurs tel que pour chaque :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.$$ et $$c(ij) \neq c(ik) \quad for \quad j \neq k$$

Veuillez noter que dans le problème ci-dessus, seuls les bords en doivent être colorés. C'est le problème qui peut être résolu dans .O ( | T | ! $T$$\mathcal{O}(|T|!)$

Mettre à jour:

Après le commentaire de Tsuyoshi Ito, j'ai mis à jour le problème. Le dénominateur passe de à . Par conséquent, le dénominateur contient les poids en dehors ainsi. C'est en fait pourquoi j'ai mentionné le graphique complet dans la définition. 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$

J'ai également ajouté une contrainte supplémentaire . Cela signifie que les bords sortants d'un nœud doivent être de couleurs différentes (mais les couleurs entrantes peuvent être les mêmes tant que l'inégalité se maintient). Cela met une limite inférieure intuitive sur le nombre de couleurs, ce qui est le maximum degrés des nœuds .$c(ij) \neq c(ik) \quad for \quad j \neq k$$T$

Comme Tsuyoshi l'a mentionné, les , et sont des entrées pour le problème et les couleurs des bords sont la sortie. T $w_{ij}$$T$$\beta$

Mise à jour 2:

Le problème n'impose pas que les bords et soient de la même couleur. e j $e_{ij}$$e_{ji}$

Il est assez simple de montrer que la formulation alternative est dure NP. La réduction provient du problème de coloration des sommets. Étant donné un graphe G avec sommets, nous créons une instance du problème ci-dessus avec sommets de sortie et sommets d'entrée. Les poids sont définis comme suit: Pour tout , soit . Pour , s'il y a une arête entre le sommet et le sommet , soit , sinon soit . De plus, laissez .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$

C'est assez évident mais difficile de décrire pourquoi la réduction est correcte. Soit montrer l'instance de la coloration du graphe et R montrer l'instance réduite du problème. Pour montrer la réduction ci - dessus donne une solution correcte , nous devons montrer que (1) chaque coloration valable pour R est valable pour C ainsi. (2) la réponse donnée par R est minime pour C .$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$

Si et j sont deux sommets adjacents de C , ils doivent avoir des couleurs différentes dans R . En effet, si i et j sont adjacents et qu'ils ont la même couleur, la fraction w j $i$$j$$\mathcal{C}$$\mathcal{R}$$i$$j$ donnerait$\frac{w_{jj}}{1+\sum_{c(i)=c(j),i \neq j} w_{ij}}$ , oùXa une valeur positive. Par conséquent, la condition ne tient pas. En outre, chaque valide (mais pas nécessairement minime) coloration pourC, est une coloration valable pourRainsi. Il s'ensuit que dans une coloration valide deC, chaque paire de nœuds adjacents a des couleurs différentes, donc la condition est valable pour toutes les arêtes colorées deRdans la solution. Étant donnéchaque coloration deCest une coloration valable pourR, la solution minimale àRdoit être une solution minimale àC ainsi. Sinon, ce n'est pas un minimum car la solution à$\frac{1}{1+X}$$X$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{C}$$\mathcal{R}$$\mathcal{R}$$\mathcal{C}$$\mathcal{C}$ donne une solution avec un plus petit nombre de couleurs.

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