Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

We have a digraph D=(V,A) and its arc set A is partitioned into classes. We can flip the classes, which means changing the direction of all the arcs in the class.

Is there any result on when can we make the digraph acyclic with this operation?

Even such special case would be interesting for me such as:

  • the underlying graph is planar, and
  • each classes form a path of same length in the underlying graph
  • and each of these undirected paths (the classes) has alternating orientation.

Thanks for the answers.

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

A teacher of mine (Zoltán Király) proved it to be NP-complete by reducing the 3-SAT problem to this problem: for each clause there should be an indirected circle with 4 edges. The classes and the starting orientation are:

  • one edge from each circle as a referential edge directed clockwise.
  • the other 3 edges of each circle represent the variables in the clause, the edges representing the same literals form one class. The orientation of the edges in a circuit representing literals of the related clause are clockwise (the same as the referential edge) if the literal is the variable, and counterclockwise if it's the negated variable.

It's easy to see that finding an acyclic orientation by fliping the classes representing the literals (we can suppose that the oriention of the referential edges is fixed) is the same as to satisfy the 3-SAT instance.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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