Problèmes «dirigés» plus faciles que leur variante «non dirigée».

28

Je présentais une conférence sur le tri des crêpes et j'ai mentionné que:

Ce qui m'a fait réfléchir. Il y a un sens dans lequel le tri "signé" est "dirigé" - vous pouvez voir le signe comme une direction (et en fait, c'est la motivation de la biologie évolutive). Mais c'est un problème plus facile! Ceci est inhabituel car généralement (au moins sur les graphiques) les problèmes dirigés sont plus difficiles (ou au moins aussi difficiles) que leurs homologues non dirigés.

En supposant une définition généreuse de «dirigé», existe-t-il des exemples de problèmes dirigés plus faciles que leurs homologues non dirigés?

ds.algorithms Suresh Venkat
la source

2

Vous pouvez considérer Horn 3SAT (chaque clause peut être représentée comme (A ET B)

C) comme une clause dirigée car elles peuvent être considérées comme des implications. Donc, ici, le cas dirigé est facile tandis que le 3SAT non dirigé est difficile.

\to

$\to$

Mohammad Al-Turkistany

1

Je me suis posé une question similaire pour une classe que j'enseignais (où nous avons utilisé LP pour approximer la solution IP): y a-t-il une classe de problèmes où trouver une solution entière était plus facile que de trouver une solution rationnelle

Gopi

17

Le comptage des circuits eulériens pour les graphes dirigés est faisable en temps polynomial en utilisant le théorème BEST , alors qu'apparemment, le même problème pour les graphes non orientés est # P-complet .

Timothy Sun
la source

Toutes les réponses sont excellentes, mais si je dois en accepter une, c'est parce que l'écart est grand et que le problème est très net.

Suresh Venkat

15

Un cas intéressant et moins connu est le suivant. Supposons que nous ayons un graphe pondéré sur les bords et le nœud racine . Nous voulons le sous-graphe de coût minimum de tel qu'il y ait chemins bord-disjoints de à chaque nœud du graphe. Lorsque c'est le problème d'arborescence au coût min dans les graphes dirigés et dans les graphes non orientés, il est équivalent au problème MST. Les deux solvables en poly-temps bien que le cas non orienté soit plus facile. Cependant, le problème est résolu poly-temps dans les graphes dirigés pour tout alors qu'il est NP-dur dans les graphes non orientés pour (car il capture le coût min. $G$ $r$ $G$ $k$ $r$ $k=1$ $k$ $k=2$ $2$ problème de sous-graphe connecté à la périphérie).

Chandra Chekuri
la source

13

Ce n'est peut-être pas le meilleur exemple, mais considérons la couverture de cycle (dirigée), où la tâche consiste à couvrir tous les sommets par des cycles (dirigés) disjoints. Dans le cas dirigé, cela peut être réduit à une correspondance bipartite et résolu en temps polynomial. Dans le cas non orienté, le problème peut être réduit à l'appariement non bipartite (et vice versa), qui est un problème plus difficile, mais toujours résolu en temps polynomial.

Daniel Marx
la source

10

Un exemple similaire plus impressionnant est le suivant: soit

un graphique pondéré dirigé (les poids peuvent être négatifs). Nous pouvons vérifier s'il y a un cycle négatif dans

utilisant l'algorithme de Ford-Bellman. Mais si

n'est pas orienté, alors le problème devient beaucoup plus difficile (mais toujours résolu poly-temps).

G

$G$

G

$G$

G

$G$

ilyaraz

C'est certainement un bon exemple, et dans le sens de ce à quoi je pensais quand j'ai posé la question.

Suresh Venkat

2

J'ai toujours eu l'impression que les "problèmes de cycles" sont plus faciles sur les graphes orientés. Peut-être y a-t-il un principe derrière cela, comme le fait que les composants connectés 2 ont "moins de structure" que les composants fortement connectés ("problèmes impliquant des cycles" = ceux qui peuvent être résolus en regardant séparément chaque composant).

Diego de Estrada

3

Diego: si une marche fermée dirigée passe par un sommet v, alors il y a un cycle dirigé passant par v. La déclaration analogue n'est pas vraie pour les graphiques non dirigés. Ainsi, dans les graphiques dirigés, nous pouvons souvent raisonner sur les promenades au lieu des cycles. Les promenades sont plus robustes et moins théoriques que les cycles, ce qui pourrait être un avantage. C'est peut-être une explication formelle de votre impression.

Daniel Marx

9

Voici un problème qui, comme je l'ai récemment réalisé, semble plus difficile dans les graphiques non dirigés que dans les graphiques dirigés.

Supposons que vous ayez un graphique avec des poids de bord positifs et négatifs et que l'on vous demande de détecter un cycle de poids négatif. Il existe un algorithme de mise à l'échelle pour ce problème pour les graphiques dirigés de Goldberg'93 (AV Goldberg. 1993. Algorithmes de mise à l'échelle pour le problème des chemins les plus courts. Dans SODA '93.) Fonctionnant dans O ( $m\sqrt{n}\log C$ $m$ $n$ $C$ $n^3, mn\log n$

$m\sqrt{n}\log C$ $n^3, mn\log n$

virgi
la source

mais ici «dur» signifie simplement en ce qui concerne les temps d'exécution (polynomiaux) des algorithmes que nous connaissons; il se pourrait que nous

manquions de

2

Voilà un autre exemple intéressant. Et félicitations ps pour le nouveau résultat incroyable.

Suresh Venkat

1

Merci, Suresh! Sur une autre note, je viens de remarquer que ilyaraz avait ma réponse dans un commentaire à la réponse de Daniel Marx ... désolé pour le doublon.

virgi

Problèmes «dirigés» plus faciles que leur variante «non dirigée».

Réponses: