Problema mínimo de conectividade flip

Formulei o seguinte problema hoje, enquanto brincava com o meu GPS. Aqui está :

Seja um gráfico direcionado, de modo que se então , ou seja, é uma orientação do gráfico não direcionado subjacente. Considere as seguintes operações:$G(V,E)$$e=(u,v) \in E$$(v,u) \notin E$$G$

• $Flip(u,v)$ : Replace an edge $(u,v)$ with an edge $(v,u)$
• $undirect(u,v)$ : Make the edge $(u,v)$ undirected

Let $s,t \in V$ be two special vertices. Consider the following optimization problems :

• Min-Flip st-connectivity : Given $G$ and two vertices $s,t$ find the minimum number of edges that need to be flipped to make a directed path from $s$ to $t$.
• Min-Flip strong-connectivity : Given $G$ find the minimum number of edges that need to be flipped to make $G$ strongly connected. If it is not possible to make $G$ strongly connected by flipping edges then output NO.
• Min-undirect strong-connectivity : Given $G$ find the minimum number of edges that need to be undirected to make $G$ strongly connected.

Note that you are not allowed to add "new" edges. You are only modifying the existing edges using the above operations. Is this problem known in the literature. If so what are the known results ?

Summary: The problems can be solved in polynomial time by finding a minimum-cost strongly connected orientation.

More detail: A theorem of Robbins tells that the edges of an undirected graph can be oriented so that the resulting directed graph is strongly connected if and only if the undirected graph is 2-edge-connected. There are several extensions, and one of them says using a polynomial-time submodular flow algorithm, we can solve the following problem in polynomial time: Given an undirected graph with edge cost (for both directions), find a minimum-cost orientation that makes the graph strongly connected. For example, see Frank's paper. A more recent algorithm is provided by Iwata and Kobayashi.

This result should be useful for solving the posed problems. The first problem can be solved by the method Tomek proposed. So we'll concentrate on the other problems.

For the second problem, we use the same construction of an edge-weighted graph as Tomek, and find a minimum-cost strongly connected orientation in polynomial time.

For the third problem, to allow both directions for each edge, we duplicate each edge, and then apply the same construction and the same algorithm. This is a valid reduction since using the same direction for duplicated edges does not affect the strong connectedness.

This is an answer for the first problem:
Consider a new weighted graph $G'=(V,E')$, where $E'=\{(u,v,0)|(u,v) \in E\} \cup \{(v,u,1)|(u,v)\in E \}$ (weights of all edges that are in $G$ are 0, and weights of 'reversed' edges are 1). Now You just have to find the shortest path from $s$ to $t$.

Min-Flip s-t connectivity is NL-complete if you phrase the decision problem as "Is there an s-t path which requires flipping at most $k$ edges?". It's NL-hard because it contains s-t connectivity as a special case for $k=0$, and it's in NL because you can guess a path from $s$ to $t$ that uses some flipped edges and traverse it one edge at a time, keeping a counter to ensure that no more than $k$ edges are traversed backward.

In my recent book, Connections in Combinatorial Optimization (Oxford University Press, 2011) a central theme is graph orientation problems, including the variations discussed above. It is known that a 2k-edge-connected graph has a k-edge-connected orientation (this is a theorem of Nash-Williams). If the graph is not 2k-edge-connected, one may be interested in deciding if a given subset F of edges is good (in the sense that F has an orientation so that the resulting mixed graph is k-edge-connected). In the book I described how this problem can be solved in polynomial time. But I do not know how to find a minimum cardinality good set.

Andras Frank

Min-Flip st-connectivity Base : calculate all the vertices that are reachable from s (T). if t is in T stop. Inductive : consider all the vertices not in T that are adjacent to T with one one flip and call this U. Calculate the vertices reachable from U call this V. If t is V stop, otherwise add V to T and continue.

Min-Flip strong-connectivity You must mean undirect because you would have a problem with : A -> B