[Solved]: Assign undirected edges in a mixed graph to make graph cyclic/acyclic

Problem Detail: What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle. It doesn’t “feel” like an NP-hard problem, but I can’t think of an easy poly-time algorithm. What about to make the graph acyclic? As R B points out in the comments, to make the graph acyclic, you can just use a topological sort on the directed edges (ignoring the undirected edges temporarily) to get an ordering of the vertices, then use that ordering to direct the undirected edges. Therefore, that problem is easy and can be solved in $O(|V|+|E|)$ time. However, orienting the edges to create a cycle is more tricky. Consider the graph:

    A   /     B --> C

In this case, simply sorting the graph to get A B C and then pointing the AC and AB edges backwards does not reveal the cycle.

Asked By : dspyz

Answered By : Emil Jeřábek

As noted by R B, the acyclic variant of the problem is solvable iff the directed part of the graph is acyclic, in which case one can take a topological sort of the directed edges, and orient undirected edges consistently with the linear order obtained. For the cyclic variant of the problem, we can use the following polynomial-time algorithm, where $G=(V,E)$ is the input graph:

for every directed edge $e=(a,b)in E$, and for every orientation $(a,b)$ of an undirected edge $e={a,b}in E$:
- if there is a path (directed where applicable) from $b$ to $a$ in $(V,Esmallsetminus{e})$:
  - find such a path $p$
  - make sure the path is simple by deleting subcycles
  - output any orientation of the undirected edges that agrees with the cycle $e,p$ and stop
if no edge worked, reject

Note that the simplicity of $p$ in particular ensures that no undirected edge appears twice in $e,p$, hence it gives a consistent orientation. Thus, if the algorithm accepts, it is correct. On the other hand, if there exists an orientation of $G$ that includes a (wlog simple) cycle $c$, and $e=(a,b)$ is any edge in $c$ (properly oriented), then $a$ is reachable from $b$ in $(V,Esmallsetminus{e})$ by means of the rest of the cycle. Thus the algorithm will accept sooner or later. In terms of complexity, both problems are NL-complete as decision problems, and the search problem versions are in FNL.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33949 Ask a Question Download Related Notes/Documents