Can we reverse directions instead?
3
-
$\begingroup$ The title and the description are very different, you might want to change one of the two. $\endgroup$– Chao XuOct 14, 2019 at 22:45
-
$\begingroup$ Yeah sorry, initially I thought the problem reduces to that and then realized it is not so changed it. $\endgroup$– HHHOct 14, 2019 at 22:49
-
$\begingroup$ 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. $\endgroup$– Sasho NikolovOct 16, 2019 at 4:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
This problem is equivalent to feedback arc set (in a tournament graph). It is NP-hard.
-
$\begingroup$ No it is not, a feedback arc set removes edges, whereas here we are only allowed to flip edges. $\endgroup$– HHHOct 14, 2019 at 22:49
-
$\begingroup$ The minimum set to remove and the minimum set to flip are identical to each other. $\endgroup$ Oct 14, 2019 at 22:50
-
$\begingroup$ 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. $\endgroup$– HHHOct 14, 2019 at 22:57
-
$\begingroup$ 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$. $\endgroup$– holfOct 15, 2019 at 7:17
-