# conversion to DAG

Can we reverse directions instead?

• The title and the description are very different, you might want to change one of the two. – Chao Xu Oct 14 '19 at 22:45
• Yeah sorry, initially I thought the problem reduces to that and then realized it is not so changed it. – HHH Oct 14 '19 at 22:49
• The current question is completely incomprehensible. Also please don't keep changing the question: it looks like the previous version was answered, so just accept the answer, and ask a new question if you have a follow-up. – Sasho Nikolov Oct 16 '19 at 4:07

## 1 Answer

This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.

• No it is not, a feedback arc set removes edges, whereas here we are only allowed to flip edges. – HHH Oct 14 '19 at 22:49
• The minimum set to remove and the minimum set to flip are identical to each other. – David Eppstein Oct 14 '19 at 22:50
• why do you think so? you can remove a set to remove cycles, but if you flip the same edges, that does not mean cycles are removed, in fact you may end up creating new cycles. – HHH Oct 14 '19 at 22:57
• The important hypothesis here is that the set is minimal. Try to prove: $G \setminus F$ is acyclic and $F$ minimum (in the sense, for every $e$, $G \setminus (F \setminus e)$ is cyclic) $\Leftrightarrow$ $(G \setminus F) \cup \bar{F}$ is acyclic. $\Leftarrow$ is trivial. For $\Rightarrow$, use the minimality of $F$ so that if you have a cycle in $(G \setminus F) \cup \bar{F}$, you can construct a cycle in $G \setminus F$. – holf Oct 15 '19 at 7:17
• Thanks man, you are right. – HHH Oct 16 '19 at 0:25