<p>This is an answer for the first problem:<br>
Consider a new weighted graph $G&#39;=(V,E&#39;)$, where $E&#39;=\{(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$.</p>

CC BY-SA 2.5
2011-03-14T20:39:26.863Z
2011-03-14T21:43:45.530Z
2011-03-14T21:43:45.530Z
Tomek Tarczynski
<p>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.</p>

CC BY-SA 2.5
2011-03-15T07:18:35.767Z
2011-03-15T07:18:35.767Z
Dave
<p>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. </p>

<p>Andras Frank</p>

CC BY-SA 3.0
2012-01-23T13:01:57.247Z
2012-01-23T13:01:57.247Z
andras frank
<p>Summary: The problems can be solved in polynomial time by finding a minimum-cost strongly connected orientation.</p>

<p>More detail: <a href="http://en.wikipedia.org/wiki/Robbins_theorem" rel="nofollow noreferrer">A theorem of Robbins</a> 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 <a href="http://dx.doi.org/10.1016/S0304-0208%2808%2972446-0" rel="nofollow noreferrer">Frank's paper</a>.  A more recent algorithm is provided by <a href="http://dx.doi.org/10.1007/s00453-008-9179-x" rel="nofollow noreferrer">Iwata and Kobayashi</a>.</p>

<p>This result should be useful for solving the posed problems.  The first problem can be solved by <a href="https://cstheory.stackexchange.com/questions/5479/minimum-flip-connectivity-problem/5483#5483">the method Tomek proposed</a>.  So we'll concentrate on the other problems.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-15T23:29:22.677Z
2011-03-16T05:27:56.470Z
2017-04-13T12:32:28.167Z
Yoshio Okamoto
<p>I formulated the following problem today while playing with my GPS. Here it is :</p>

<p>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 :</p>

<ul>
<li>$Flip(u,v)$ : Replace an edge $(u,v)$ with an edge $(v,u)$</li>
<li>$undirect(u,v)$ : Make the edge $(u,v)$ undirected</li>
</ul>

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

<ul>
<li>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$.</li>
<li>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.</li>
<li>Min-undirect strong-connectivity : Given $G$ find the minimum number of edges that need to be undirected to make $G$ strongly connected.</li>
</ul>

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

CC BY-SA 2.5
2011-03-14T17:59:09.530Z
You mean to say minimum number of edges that **need to be** flipped right ?
Gaurav Kanade
CC BY-SA 2.5
2011-03-14T18:09:28.383Z
@Gaurav : Yes. I corrected it.
Shiva Kintali
CC BY-SA 2.5
2011-03-14T22:08:21.447Z
For the third problem, do you mean an undirected edge can be traced in both directions?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-15T06:14:18.423Z
@Yoshio : Yes. Undirected edges can be used in both directions to determine paths.
Shiva Kintali
CC BY-SA 3.0
2013-05-11T15:11:40.940Z
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
<ds.algorithms><graph-algorithms>
Minimum Flip Connectivity Problem
Shiva Kintali
# Minimum Flip Connectivity Problem

(Asked by: username_0 on 2011-03-14)

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 ?

**Tags:** ds.algorithms, graph-algorithms
> **Comments:**
> **username_1**: You mean to say minimum number of edges that **need to be** flipped right ?  
> **username_0**: @Gaurav : Yes. I corrected it.  
> **username_2**: For the third problem, do you mean an undirected edge can be traced in both directions?  
> **username_0**: @Yoshio : Yes. Undirected edges can be used in both directions to determine paths.  
> **username_3**: 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.  

---

## 4 answers

### Answer by username_2 on 2011-03-15. Score: 19 | Accepted answer

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

More detail: [A theorem of Robbins](http://en.wikipedia.org/wiki/Robbins_theorem) 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](http://dx.doi.org/10.1016/S0304-0208%2808%2972446-0). A more recent algorithm is provided by [Iwata and Kobayashi](http://dx.doi.org/10.1007/s00453-008-9179-x).

This result should be useful for solving the posed problems. The first problem can be solved by [the method Tomek proposed](https://cstheory.stackexchange.com/questions/5479/minimum-flip-connectivity-problem/5483#5483). 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.


---

### Answer by username_4 on 2011-03-14. Score: 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$.


---

### Answer by username_5 on 2011-03-15. Score: 3

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.


---

### Answer by username_6 on 2012-01-23. Score: 2

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


---

