Question

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.

Answer 1

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.