-4
$\begingroup$

Can we reverse directions instead?

$\endgroup$
3
  • $\begingroup$ The title and the description are very different, you might want to change one of the two. $\endgroup$
    – Chao Xu
    Oct 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$
    – HHH
    Oct 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$ Oct 16, 2019 at 4:07

1 Answer 1

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ No it is not, a feedback arc set removes edges, whereas here we are only allowed to flip edges. $\endgroup$
    – HHH
    Oct 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$
    – HHH
    Oct 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$
    – holf
    Oct 15, 2019 at 7:17
  • $\begingroup$ Thanks man, you are right. $\endgroup$
    – HHH
    Oct 16, 2019 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.