Énumération de toutes les paires de chemins disjoints

Etant donné un graphe orienté et deux sommets . Une paire de chemins simples de à est disjointe de bord s'ils ne partagent pas de bord.$G = (V,E)$$s,t \in V$$p_1,p_2$$s$$t$

En utilisant le débit max, il est facile de décider s'il existe une paire de chemins disjoints de bord de à . Maintenant, existe-t-il un algorithme polynomial de temporisation pour énumérer toutes les paires de chemins disjoints de bord de à ?$s$$t$$s$$t$

Je crois que la réponse d'Artem Kaznatcheev est correcte, mais elle ne donne pas d'espace polynomial. Voici donc une approche différente qui devrait fonctionner un peu mieux à cet égard.

En utilisant le flux max, il est possible de résoudre un problème un peu plus général: trouver une paire de chemins disjoints d'arête entre deux sommets {s1, s2} et une autre paire de sommets {t1, t2}, mais sans contrôler quel sommet source est connecté à quel sommet de destination.

Supposons que nous ayons un graphe G et les sommets s1, s2, t1, t2 pour lesquels nous voulons lister toutes les paires de chemins. Trouvez une seule paire de chemins P1, P2 et laissez e = (s1, v) être le premier bord de l'un de ces chemins. Ensuite, nous pouvons diviser l'espace du problème en deux sous-problèmes: les paires de chemins qui utilisent e sont les mêmes que les chemins de {v, s2} à {t1, t2} dans G-s1, et les paires de chemins qui n'utilisent pas e sont les mêmes que les chemins de {s1, s2} à {t1, t2} dans Ge. Réexaminez dans ces deux sous-problèmes et (pour éviter la duplication) ne signalez un chemin que lorsque vous êtes au bas de la récursivité.

C'est la première fois que je lis sur les algorithmes de retard polynomial, donc je ne suis pas sûr à 100% de ma réponse, mais je pense que quelque chose comme ce qui suit devrait fonctionner.

Choisissez une convention pour représenter les chemins qui ont un ordre total naturel défini dessus. (Un exemple serait juste de lister les sommets du chemin et de les ordonner lexicographiquement). Choisissez votre structure de données préférée sur place qui prend en charge la recherche logarithmique et insérez (par exemple, un arbre rouge-noir). Soit votre graphique$<$$D$$G$

Définissez un algorithme :$F$

$F(s,t,G, ^*D)$ :

(ici signifie une référence à une infrastructure de données in situ )$^*D$$D$

1. exécutez votre algorithme poly-temps pour renvoyer une paire de chemins bord-disjoints avec de à .$(P,Q)$$P < Q$$s$$t$

2. Si se trouve pas dans .$(P,Q)$$D$

   2.1. Insérez dans (et sortez si vous êtes supposé sortir pendant que l'algorithme s'exécute).$(P,Q)$$D$

   2.2. Pour chaque bord exécutez$uv \in E(P\cup Q)$$F(s,t,G - \{uv\}, ^*D)$

Maintenant, pour énumérer tous vos chemins, créez un vide et pour chaque paire avec (si le graphique n'est pas orienté, sinon) exécutez . Vous afficherez chaque chemin la première fois que vous les verrez, et vous aurez également une belle structure de données consultable qui contient tous les chemins lorsque vous avez terminé. Notez que cet algorithme s'exécute également en temps polynomial dans la taille de l'entrée + sortie (tout comme n'importe quel algorithme de retard polynomial).$D$$s,t \in V(G)$$s < t$$s \neq t$$F(s,t,G,*D)$

Je doute que ce soit la meilleure façon de le faire, en particulier cette approche n'est pas dans (en taille de l'entrée). Je pense qu'en réfléchissant bien, vous pourriez trouver quelque chose qui fonctionne dans , bien qu'il ne puisse pas construire la structure de données au fur et à mesure.$PSPACE$$PSPACE$

Birmelé et al montrent un algorithme de retard partir de la version sommet-disjoint du problème dans "Efficient Bubble Enumeration in Directed Graphs".$O(m)$