5
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com Dec 6 '14 at 22:42

This question came from our site for theoretical computer scientists and researchers in related fields.

8
$\begingroup$

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,E\smallsetminus\{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,E\smallsetminus\{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.

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