Problèmes de graphes NP-Complete sur les graphes orientés mais polynomiaux sur les graphes non orientés

Je recherche des problèmes connus pour être des PNJ pour les graphes dirigés mais qui ont un algorithme polynomial pour les graphes non orientés.

J'ai vu la question concernant l'inverse des problèmes «dirigés» qui sont plus faciles que leur variante «non dirigée» , mais je recherche la dureté du côté orienté.

Par exemple, l' ensemble de bords de rétroaction est connu pour être NPC sur temps dirigé mais polynomial résoluble sur les graphiques non dirigés.

Quels autres problèmes naturels ont la même propriété?

Le premier problème qui me vient à l'esprit est le problème des 2 chemins (ou plus généralement du problème des k-chemins). Étant donné et ( s 2 , t 2 ) , trouvez deux chemins disjoints de s 1 à t 1 et s 2 à t 2 , respectivement. Le problème est NPC pour les graphes dirigés mais résolvable en temps polynomial pour les graphes non orientés (bien que non trivial).$(s_1,t_1)$$(s_2,t_2)$$s_1$$t_1$$s_2$$t_2$

$NP$

Dans le problème de coloration des chemins, on nous donne un arbre T et une collection de chemins sur cet arbre (l'idée est que T est un réseau de communication et les chemins sont des demandes de communication). Nous voulons colorer les chemins avec un nombre minimum de couleurs afin que deux chemins qui partagent un bord prennent des couleurs distinctes.

Ce problème est connu pour être résolu dans le temps polynomial si T est un arbre non orienté à degrés bornés. Il est cependant NP-complet si T est un arbre binaire bi-dirigé. Je crois que les deux résultats sont donnés dans le document ci-dessous.

[1] T. Erlebach et K. Jansen. "La complexité de la coloration des chemins et de l'ordonnancement des appels". Informatique théorique, 255 (1-2): 33–50, 2001.

Si je ne me trompe pas, obtenir une approximation à facteur constant pour l'arbre de Steiner est NP-difficile sur les graphiques dirigés mais est P-temps sur les graphiques non orientés.