Sous-graphique contenant tous les nœuds et les bords qui font partie de chemins st simples simples de longueur limitée dans un graphique non orienté

Assez similaire à ma question précédemment publiée . Cette fois cependant, le graphique n'est pas orienté.

Donné

• Un graphe non orienté sans arêtes multiples ni boucles,$G$
• Un sommet source ,$s$
• Un sommet cible $t$ ,
• Longueur maximale de trajet $l$ ,

Je cherche $G'$ - Un sous-graphe de $G$ qui contient tout sommet et toute arête dans $G$ (et seulement ceux), qui font partie d'au moins un chemin simple de $s$ à $t$ de longueur $\leq l$ .

Remarques:

• Je n'ai pas besoin d'énumérer les chemins.
• Je recherche un algorithme efficace (temps et mémoire), car j'ai besoin de l'exécuter sur de très gros graphes (10 ^ 8 sommets, 10 ^ 9 arêtes).

Eh bien, le problème est en après tout. Je garderai la réponse précédente car elle fonctionne également pour le cas dirigé (qui est NPC, comme répondu sur l'autre question), et montre que c'est par rapport à .F P T $P$$FPT$$l$

Dans le cas non orienté, il est résoluble, de manière déterministe via le flux de coûts minimum (cela peut ne pas fonctionner sur les échelles auxquelles vous faites référence dans la question, mais c'est mieux que l'algorithme exponentiel.

La procédure suivante décidera si une arête doit faire partie du graphe de sortie. Afin de répondre au problème d'origine, il suffit de boucler sur tous les bords.$e=(u,v)\in E$

Pour créer le réseau de flux, procédez comme suit:

Étape 1: Développez pour avoir un sommet et remplacez par les arêtes (elles sont dirigées comme faisant partie du réseau d'écoulement ), définissez leur coût sur 0.x e e ( u , x e ) , ( x e , u ) , ( v , x e ) , ( x e , v $e$$x_e$$e$$(u,x_e),$$(x_e,u),(v,x_e),(x_e,v)$

Étape 2: remplacez chaque sommet , à l'exception de par deux sommets et , et ajoutez une arête . Définissez le coût de ces bords sur 1.x e t - t + ( t - , t +$t$$x_e$$t^-$$t^+$$(t^-,t^+)$

Étape 3: Remplacez chaque bord par les bords . Définissez le coût de ces bords sur 0.( a + , b - ) , ( b + , a -$\{a,b\}\in E$$(a^+,b^-),(b^+,a^-)$

Étape 4: Ajoutez un nouveau sommet et ajoutez les arêtes avec le coût 0. ( s , y e ) , ( t , y e$y_e$$(s,y_e),(t,y_e)$

Étape 5: définissez toutes les capacités sur 1.

Exécutez maintenant l'algorithme de flux de coût min, en recherchant un flux de valeur 2 de à .y $x_e$$y_e$

Une analyse:

• Chaque flux à 2 valeurs de à est une union d'un chemin et d'un chemin .y e x e ⇝ s → y x e ⇝ t → y $x_e$$y_e$$x_e\leadsto s\to y_e$$x_e\leadsto t\to y_e$
• Les chemins sont disjoints, car pour chaque sommet il n'y a qu'une capacité dans l' arc .( t - , t +$t$$(t^-,t^+)$
• Les chemins renvoyés sont les deux chemins dont la somme des distances est minimale, et c'est aussi le coût du flux trouvé. Cela nous permet d'ajouter au graphique de sortie ou de le supprimer autrement.$e$

Voici une mauvaise réponse: il génère des sommets qui font partie de chemins non simples de à et qui ne font partie d'aucun chemin simple de à de longueur . La réponse pourrait toujours être pertinente pour la demande du demandeur, donc je la laisse ici.t s t ≤ $s$$t$$s$$t$$\le \ell$

Voici un algorithme qui s'exécute dans le temps (et est en fait plus rapide que cela lorsque est petit).$O(|V|+|E|)$$\ell$

L'algorithme exécute une recherche BFS à partir de qui se termine à depth . Ce BFS donne un ensemble de tous les sommets accessibles à partir de avec un chemin de longueur au plus , et il calcule également les distances pour chaque . Ensuite, je ferais la même chose à partir de et j'obtiendrais l'ensemble et les distances à partir de . Enfin, les sommets que vous recherchez sont exactement . Les arêtes sont exactement ces arêtes dans ($s$$\ell$$V_s$$s$$\ell$$dist(s,v)$$v \in V_s$$t$$V_t$$t$$V_{solution}=\{ v : v \in V_s \cap V_t, dist(s,v)+dist(t,v) \le \ell \}$$E[V_{solution}]$$=(v,u) \in E : u,v \in V_{solution}$).

Le temps d'exécution de cet algorithme est sûrement car il ne fait que deux BFS. Mais le temps d'exécution est en fait qui sera beaucoup plus petit que la taille du graphe lorsque les -radius voisinages de et sont petits.$O(|V|+|E|)$$O(|V_s| + |V_t| + |E[V_s]|+|E[V_t]|)$$\ell$$s$$t$

Edit: il existe probablement un algorithme un peu plus rapide dans la pratique qui effectue un BFS à partir de et de profondeur uniquement plutôt que . Cela découvre tous les chemins, puis avec un peu de comptabilité, vous pouvez trouver tous les sommets. Cela réduit le temps d'exécution d'une racine carrée dans le cas d'un grand graphique à aléatoire lorsque est petit.$s$$t$$\ell/2$$\ell$$\ell$

Ceci est destiné à être un commentaire, mais il est trop long pour poster un commentaire.

Vous pourriez également être intéressé par des clés de graphe ou des émulateurs pour vos besoins. Une clé d'un graphe est un sous-graphe avec peu d'arêtes, mais des distances approximativement préservées. Un émulateur est un graphe dont les arêtes peuvent être pondérées.H = ( V , E ′ ) H = ( V , E ′ , w $G = (V, E)$$H = (V, E')$$H = (V, E', w)$

Le meilleur résultat pour les clés est arêtes et une erreur additive de +6 sur les estimations de distance dans le graphique. Le meilleur résultat pour les émulateurs est arêtes et une erreur additive de +4. On ne sait pas non plus si nous pouvons battre , même si l'erreur peut être polylogarithmique.O ( n quatre / 3 ) O ( n quatre / 3$O(n^{4/3})$$O(n^{4/3})$$O(n^{4/3})$

Si cela vous semble utile, je peux essayer de trouver les constructions pertinentes pour vous.