-4
$\begingroup$

Can we reverse directions instead?

$\endgroup$
  • $\begingroup$ The title and the description are very different, you might want to change one of the two. $\endgroup$ – Chao Xu Oct 14 '19 at 22:45
  • $\begingroup$ Yeah sorry, initially I thought the problem reduces to that and then realized it is not so changed it. $\endgroup$ – HHH Oct 14 '19 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 Nikolov Oct 16 '19 at 4:07
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ No it is not, a feedback arc set removes edges, whereas here we are only allowed to flip edges. $\endgroup$ – HHH Oct 14 '19 at 22:49
  • $\begingroup$ The minimum set to remove and the minimum set to flip are identical to each other. $\endgroup$ – David Eppstein Oct 14 '19 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$ – HHH Oct 14 '19 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$ – holf Oct 15 '19 at 7:17
  • $\begingroup$ Thanks man, you are right. $\endgroup$ – HHH Oct 16 '19 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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