Complexité de l'homomorphisme digraphique à un cycle orienté

9

Étant donné un graphe orienté fixe (digramme) , le problème de décision -coloration demande si un digramme d'entrée a un morphisme de . (Un homomorphisme de à est un mappage de à qui préserve les arcs, c'est-à-dire que si est un arc de , alors est un arc de )D G D G D f V ( G ) V ( D ) u v G f ( u ) f ( v ) DDggFV(g)V()uvgF(u)F(v)

La classe des problèmes de COLORATION est fortement liée à la conjecture de dichotomie pour les CSP déclarée par Feder et Vardi (accessible sur Citeseer ).

Dans cet article de 2001 (accessible sur la page de l'auteur, ici ), Feder prouve un théorème de dichotomie lorsque est un cycle orienté (par cycle orienté je veux dire un cycle non orienté où chaque arête est remplacée par un seul arc, qui peut être orienté arbitrairement) en d'autres termes, il montre que pour tout cycle orienté , -COLORING est soit solvable en temps polynomial, soit NP-complet.D

Malheureusement, la classification de Feder est très non triviale et non explicite, car la complexité de nombreux cas est liée à la complexité de certaines variantes restreintes de SAT qui dépendent de l'orientation. En regardant le document, je n'ai pas pu déterminer la réponse à ma question:

Question: Quelle est la plus petite taille d'un cycle orienté tel que -COLORATION soit NP-complet?D

La réponse pourrait être énoncée quelque part dans la littérature, mais je ne l'ai pas trouvée.


Éditer:Permettez-moi de donner plus de détails sur le classement de Feder. Feder montre que tout cycle orienté NP-complet doit être équilibré, c'est-à-dire avoir le même nombre d'arcs dans les deux directions (il a donc même un ordre). Ensuite, considérez les "niveaux" induits par l'orientation (commencez à faire le tour du cycle à un sommet arbitraire; si un arc va à droite, vous montez de 1, si un arc va à gauche, vous descendez de 1). Ensuite, s'il y a au plus un "parcours haut-bas", c'est polynomial. S'il y a au moins 3 "exécutions" de ce type et que le cycle est un noyau, il est NP-complet. (Dans l'exemple d'András dans les commentaires, il y a trois de ces "exécutions", mais le cycle n'est pas un noyau.) Les cas les plus délicats sont ceux avec deux "exécutions de haut en bas". Certains sont difficiles, certains polynomiaux, et Feder les relie à des problèmes SAT spéciaux pour obtenir une dichotomie.

En tant que question intermédiaire: quel est le plus petit cycle orienté qui a trois cycles «haut-bas» et est un noyau? Un tel exemple serait NP-complet par la discussion ci-dessus.

Florent Foucaud
la source
Je ne me souviens pas d'une réponse rapide dans la littérature (peut-être que Barnaby Martin ou Florent Madelaine le sauraient). Cependant, la taille est au maximum de 6 sommets et 6 arêtes dirigées, car on peut réduire -Coloration à D -Coloration pour un digraphe à six sommets D en remplaçant chaque arête non orientée dans les graphiques par deux arcs pointant vers un nouveau sommet entre ses points de terminaison. K3DD
András Salamon
Merci András. Cependant, je pense que la réponse doit être plus large car le cœur de cet exemple est tout simplement un digraphe avec un arc unique, qui est soluble dans le temps polynomial ...
Florent Foucaud
Tu as raison, la construction que j'ai proposée est trop simple.
András Salamon
J'ai demandé à Florent Madelaine et Barnaby Martin, mais ils ne connaissent pas directement la réponse, bien qu'ils semblent être intéressés :-) Mon collègue a demandé à Feder par email la semaine dernière, mais il n'a pas (encore) répondu.
Florent Foucaud
Ma deuxième impulsion a été d'utiliser une version rigidifiée du triangle. Cependant, avec le gadget de rigidité de Chvátal et al. (JCT 1971) le triangle rigidifié semble alors nécessiter un nombre de sommets d'au moins 9v + 36, si le graphe d'entrée a v sommets, et il n'est pas clair comment modifier ces gadgets en chemins. On pourrait peut-être plutôt utiliser un chemin dirigé rigide pour remplacer chaque arête, mais je ne sais pas comment le faire tout en conservant la possibilité de mapper n'importe quelle arête du graphique à n'importe quelle arête du triangle (mais nulle part ailleurs), car le la manière évidente de le faire est d'exiger la symétrie.
András Salamon

Réponses:

5

Pour la question intermédiaire (un noyau avec trois pistes de haut en bas), qu'en est-il?

Quelques notations: je vais décrire les exécutions par des mots dans , avec par exemple l l r l correspondant à un sous-graphe . Le niveau augmente sur r arcs et diminue sur l arcs, et je suppose que son minimum est 0 . Certaines contraintes simples sont:{l,r}llrlrl0

  • Il ne peut pas y avoir de course composée uniquement de s ou seulement de r s, car sinon il y a un homomorphisme évident de D à cette course (mappage de chaque nœud de D à celui de même niveau). Cela implique également que le niveau maximum doit être d'au moins 3 .lrDD3
  • Si le niveau maximum était de , tous les parcours de haut en bas (resp de bas en haut) seraient de la forme l l r ( l r ) i l l (resp. R r l ( r l ) i r r ) ; encore une fois, il n'est pas très difficile de trouver un homomorphisme de D à la course qui minimise i .3llr(lr)illrrl(rl)irr)Di

Cependant, pour le niveau maximum il existe une solution, de longueur 36 : considérons D donné par ( r r r l r r l l l r l l ) 3 . Celui-ci a les courses de haut en bas requises et est un noyau (voir ci-dessous). Par les contraintes ci-dessus, il est nécessairement minime, car chaque passage n'a qu'un seul bord "arrière".436D(rrrlrrlllrll)3

Pour nous convaincre qu'il s'agit d'un noyau, nommons d'abord les sommets ( ). Les sommets inférieurs (c'est-à-dire de niveau 0 ) sont v 1 , v 13 , v 25 . Tout homomorphisme φ de D vers un sous-graphe doit conserver des niveaux, et en particulier φ ( v 1 ) { v 1 , v 13 , v 25 } ; modulo l'automorphisme évident v ivv1,,v360v1,v13,v25φDφ(v1){v1,v13,v25} , il suffit de considérer le casφ( v 1 )= v 1 . Considérons le voisinage de v 1 enD(annoté de niveaux):vivi+12φ(v1)=v1v1D

v34(1)v35(2)v36(1)v1(0)v2(1)v3(2)v4(3)v5(2)v6(3)v7(4)

En commençant par , nous avons φ ( v 2 ) { v 36 , v 2 } . Mais si φ ( v 2 ) = v 36 , alors φ ( v 3 ) = v 35 , et nous n'avons pas de valeur possible pour φ ( v 4 ) . On obtient φ ( v 2 ) = vφ(v1)=v1φ(v2){v36,v2}φ(v2)=v36φ(v3)=v35φ(v4) . Suivant φ ( v 5 ) { v 3 , v 5 } , mais pour φ ( v 5 ) = v 3 on obtient φ ( v 6 ) = v 4 , sans valeur possible pour φ ( v 7 )φ(v2)=v2,φ(v3)=v3,φ(v4)=v4φ(v5){v3,v5}φ(v5)=v3φ(v6)=v4φ(v7). Alors doit être l'identité sur l'ensemble du terme v 1... v 7 et en répétant le même argument pour les courses restantes, la même chose est vraie sur tous D . En particulier, φ ne mappe pas D sur un sous-graphe approprié.φv1v7DφD

Klaus Draeger
la source
3
Cette même analyse montre que tous les cycles orientés équilibrés avec deux séries qui sont des noyaux ont une longueur d'au moins 24, non? Cela donne donc une limite inférieure sur la réponse au problème principal.
David Eppstein
Oui, bon point.
Klaus Draeger
1
Super, merci, c'est très utile! Pouvons-nous nous convaincre à la main que c'est un noyau? (notez qu'il existe un algorithme polynomial pour vérifier si un cycle orienté est un noyau: créez l'ensemble de | V ( D ) | sous-chemins orientés { D - a tel que a est un arc de D } , et puis vérifiez si D correspond à l'un de ces chemins; cela peut être fait en polytime, voir Gutjahr et al: sciencedirect.com/science/article/pii/0166218X9290294K )D|V(D)|{DaaD}D
Florent Foucaud
1
@FlorentFoucaud J'ai ajouté un peu montrant que est un noyau. D
Klaus Draeger