Quelle est la complexité de ce problème de coloration des bords?

17

Récemment, j'ai rencontré la variante suivante de coloration des bords.

Étant donné un graphe connexe non orienté, trouvez une coloration des arêtes qui utilise le nombre maximal de couleurs tout en satisfaisant également la contrainte selon laquelle, pour chaque sommet , les arêtes incidentes à utilisent au plus deux couleurs.vv

Ma première supposition est que le problème est NP-difficile. Les épreuves classiques NP-hard pour les problèmes de coloration des graphes sont principalement par réduction de 3SAT. Mais à mon avis, ces preuves ne sont pas utiles pour ce problème car les arêtes incidentes à un sommet peuvent être colorées de la même couleur, nous ne pouvons donc pas construire de composants logiques dans le graphique.

Ce problème pourrait-il être NP-difficile? Si oui, qu'est-ce qu'une preuve? Si nous ne pouvons pas affiner une preuve, existe-t-il une méthode pour déterminer la complexité de ce problème?

Merci!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
la source
Peut-être que la coloration hypergraphique mixte ou liée à la couleur pourrait être un début? Par exemple, dx.doi.org/10.1016/j.disc.2008.04.019
András Salamon
Il semble que votre problème soit en P, en deux étapes: (1) votre problème équivaut à trouver un sous-ensemble de taille maximale des arêtes de sorte que chaque sommet ait un degré au plus deux, et (2) ce dernier problème semble être en P par, disons, réduction à l'appariement. En ce qui concerne (1), notez que toute solution à votre problème avec k couleurs donne un sous-graphique de degré 2 de taille k (il suffit de conserver un bord de chaque couleur), et inversement tout sous-graphique de degré 2 de taille k donne une solution avec k couleurs (coloriez simplement chaque bord du sous-graphique de sa propre couleur, coloriez le reste des bords avec l'une des couleurs). Qu'est-ce que je rate?
Neal Young
Je suis désolé qu'il y ait plusieurs erreurs dans votre réponse. Au début, le problème "trouver un sous-ensemble de taille maximale des arêtes tel que chaque sommet ait un degré au plus deux", est NP-difficile, réduction à 3SAT (je ne sais pas vraiment comment cela pourrait avoir une réduction à l'appariement). De plus, «tout sous-graphe de degré 2 de taille k» ne donne pas «une solution avec k couleurs», par exemple, Graphique complet. Merci tout de même.
RIC_Eien
Oui tu as raison. À propos de (2), l'étape "colorier le reste des bords avec l'une des couleurs" peut donner des bords de sommet de trois couleurs. Séparément, Marek Chrobak m'a suggéré l'algorithme suivant. Je pense que cela donne une approximation de 3: (i) trouver un maximum correspondant à M; (ii) colorer chaque bord en M de sa propre couleur unique; (iii) colorier les bords restants en blanc.
Neal Young
@RIC_Eien: Au risque d'être encore plus embarrassé. Êtes-vous sûr que "le problème" de trouver un sous-ensemble de taille maximale des arêtes tel que chaque sommet ait un degré au plus deux ", est NP-difficile"? Étant donné G = (V, E), créer bipartite G2 = (U, W, E2), où pour chaque sommet v dans V il y a v 'dans U et v' 'dans W, et E2 = {(u', w ''): (u, w) dans E}. Ensuite, les correspondances dans G2 correspondent aux ensembles d'arêtes de degré 2 dans G, et la correspondance préserve la taille? (Comme chaque k-cycle C dans G correspond dans G2 à un cycle de 2k (si k impair) ou à deux k-cycles (si k pair).) Ainsi, l'appariement max dans G2 le résout. Qu'est-ce qui me manque cette fois?
Neal Young

Réponses:

15

Ce problème est NP-hard et APX-hard; voir: Adamaszek et Popa, Approximation and Hardness Results for the Maximum Edge -coloring Problemq , Lecture Notes in Computer Science 6507 (2010) 132-143 .

Les aspects de complexité paramétrés de ce problème sont traités dans cet article récent .

vb le
la source
Je réfléchis depuis longtemps à ce joli problème ... Pouvez-vous décrire la réduction? Je n'ai pas accès au journal. Merci!
user13667
5
@ user13667 Vous pouvez demander aux auteurs de vous envoyer une copie de leur article. Je pense qu'ils seraient heureux de le faire.
vb le
5
La question connexe de trouver une coloration qui maximise le nombre de couleurs tout en minimisant la taille du plus grand groupe de couleurs a également été étudiée. Par exemple, cette thèse de maîtrise a plusieurs résultats détaillés.
Neeldhara