Problème de connectivité Flip minimum

J'ai formulé le problème suivant aujourd'hui en jouant avec mon GPS. C'est ici :

Soit $G(V,E)$ un graphe orienté tel que si $e=(u,v) \in E$ alors $(v,u) \notin E$ , c'est-à-dire que est une orientation du graphe non orienté sous-jacent. Considérez les opérations suivantes:$G$

• $Flip(u,v)$ : remplacer un bord$(u,v)$ par un bord$(v,u)$
• $undirect(u,v)$ : rendre le bord$(u,v)$ non orienté

Soit $s,t \in V$ deux sommets spéciaux. Tenez compte des problèmes d'optimisation suivants:

• Min-Flip st-connectivité: étant donné et deux sommets s , t trouve le nombre minimum d'arêtes qui doivent être inversées pour faire un chemin dirigé de s à t .$G$$s,t$$s$$t$
• Min-Flip forte connectivité: étant donné trouver le nombre minimum d'arêtes qui doivent être inversées pour rendre G fortement connecté. S'il n'est pas possible de rendre G fortement connecté en inversant les bords, alors sortez NO.$G$$G$$G$
• Min-connectivité forte indirecte: étant donné trouver le nombre minimum d'arêtes qui doivent être non orientées pour rendre G fortement connecté.$G$$G$

Notez que vous n'êtes pas autorisé à ajouter de "nouveaux" bords. Vous modifiez uniquement les bords existants à l'aide des opérations ci-dessus. Ce problème est-il connu dans la littérature? Si oui, quels sont les résultats connus?

Résumé: Les problèmes peuvent être résolus en temps polynomial en trouvant une orientation fortement connectée à coût minimum.

Plus de détails: un théorème de Robbins indique que les bords d'un graphe non orienté peuvent être orientés de sorte que le graphe orienté résultant est fortement connecté si et seulement si le graphe non orienté est connecté à 2 arêtes. Il existe plusieurs extensions, et l'une d'elles dit qu'en utilisant un algorithme de flux sous-modulaire en temps polynomial, nous pouvons résoudre le problème suivant en temps polynomial: étant donné un graphique non orienté avec un coût de bord (pour les deux directions), trouver une orientation de coût minimum qui fait le graphique est fortement connecté. Par exemple, voir l'article de Frank . Un algorithme plus récent est fourni par Iwata et Kobayashi .

Ce résultat devrait être utile pour résoudre les problèmes posés. Le premier problème peut être résolu par la méthode proposée par Tomek . Nous allons donc nous concentrer sur les autres problèmes.

Pour le deuxième problème, nous utilisons la même construction d'un graphe pondéré par les bords que Tomek, et trouvons une orientation fortement connectée à coût minimum en temps polynomial.

Pour le troisième problème, pour permettre les deux directions pour chaque arête, nous dupliquons chaque arête, puis appliquons la même construction et le même algorithme. Il s'agit d'une réduction valide car l'utilisation de la même direction pour les bords dupliqués n'affecte pas la forte connectivité.

$G'=(V,E')$$E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$$G$$s$$t$

$k$$k=0$$s$$t$$k$

Dans mon récent livre, Connections in Combinatorial Optimization (Oxford University Press, 2011), un thème central est les problèmes d'orientation des graphes, y compris les variations discutées ci-dessus. Il est connu qu'un graphe connecté à 2k bords a une orientation connectée à k bords (c'est un théorème de Nash-Williams). Si le graphe n'est pas connecté à 2k bords, on peut être intéressé à décider si un sous-ensemble donné F de bords est bon (dans le sens où F a une orientation de sorte que le graphe mixte résultant soit connecté à k bords). Dans le livre, j'ai décrit comment ce problème peut être résolu en temps polynomial. Mais je ne sais pas comment trouver un bon ensemble de cardinalité minimum.

Andras Frank

Min-Flip base de connectivité st: calcule tous les sommets accessibles à partir de s (T). si t est en T stop. Inductif: considérez tous les sommets qui ne sont pas dans T qui sont adjacents à T avec un seul flip et appelez cet U. Calculez les sommets accessibles à partir de U appelez ce V. Si t est V stop, sinon ajoutez V à T et continuez.

Min-Flip forte-connectivité Vous devez vouloir dire indirect car vous auriez un problème avec: A -> B