# conversion to DAG

• The title and the description are very different, you might want to change one of the two. Oct 14, 2019 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, 2019 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. Oct 16, 2019 at 4:07

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, 2019 at 22:49
• The minimum set to remove and the minimum set to flip are identical to each other. Oct 14, 2019 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, 2019 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, 2019 at 7:17
• Thanks man, you are right.
– HHH
Oct 16, 2019 at 0:25