25
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ You mean to say minimum number of edges that need to be flipped right ? $\endgroup$ – Gaurav Kanade Mar 14 '11 at 17:59
  • $\begingroup$ @Gaurav : Yes. I corrected it. $\endgroup$ – Shiva Kintali Mar 14 '11 at 18:09
  • $\begingroup$ For the third problem, do you mean an undirected edge can be traced in both directions? $\endgroup$ – Yoshio Okamoto Mar 14 '11 at 22:08
  • $\begingroup$ @Yoshio : Yes. Undirected edges can be used in both directions to determine paths. $\endgroup$ – Shiva Kintali Mar 15 '11 at 6:14
  • $\begingroup$ Related: tcs.uni-luebeck.de/downloads/papers/2011/orient-ilp.pdf $\endgroup$ – user4379 Mar 24 '11 at 23:25
19
$\begingroup$

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.

$\endgroup$
20
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.