Minimum Flip Connectivity Problem

Question

I formulated the following problem today while playing with my GPS. Here it is :

Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of the underlying undirected graph. Consider the following operations :

$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 ?

You mean to say minimum number of edges that need to be flipped right ? — Gaurav Kanade, Mar 14 '11 at 17:59
For the third problem, do you mean an undirected edge can be traced in both directions? — Yoshio Okamoto, Mar 14 '11 at 22:08
@Yoshio : Yes. Undirected edges can be used in both directions to determine paths. — Shiva Kintali, Mar 15 '11 at 06:14
Related: http://www.tcs.uni-luebeck.de/downloads/papers/2011/orient-ilp.pdf — , Mar 24 '11 at 23:25
This paper may be helpful. http://www.springerlink.com/content/kd15b2l8atmf9j8n/ — , Jan 23 '12 at 15:49
A result related to the 2nd and 3rd questions is that to achieve an orientation in which s and t are k-edge-connected, we always have a min-flip-sequence, in which the s-t edge-connectivity never decreases. This follows from the fact that the s-t k-connected orientations form a partial cube. — László Kozma, May 11 '13 at 15:11

Tomek Tarczynski · Answer 1 · 2011-03-14T21:43:45.530

20

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$.

edited Mar 14 '11 at 21:43

answered Mar 14 '11 at 20:39

Tomek Tarczynski

598
4
10

score 19 · Accepted Answer · edited Apr 13 '17 at 12:32

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.

score 3 · Answer 3 · answered Mar 15 '11 at 07:18

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.

score 2 · Answer 4 · answered Jan 23 '12 at 13:01

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

score 0 · Answer 5 · answered Mar 14 '11 at 19:51

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

Minimum Flip Connectivity Problem

5 Answers5