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

CC BY-SA 4.0
2019-10-14T22:49:53.320Z
No it is not, a feedback arc set removes edges, whereas here we are only allowed to flip edges.
HHH
CC BY-SA 4.0
2019-10-14T22:50:30.847Z
The minimum set to remove and the minimum set to flip are identical to each other.
David Eppstein
CC BY-SA 4.0
2019-10-14T22:57:10.533Z
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
CC BY-SA 4.0
2019-10-15T07:17:09.543Z
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
CC BY-SA 4.0
2019-10-16T00:25:25.583Z
Thanks man, you are right.
HHH
CC BY-SA 4.0
2019-10-13T21:11:56.953Z
2019-10-13T21:11:56.953Z
Laakeri
<p>Can we reverse directions instead?</p>

CC BY-SA 4.0
2019-10-14T22:45:12.810Z
The title and the description are very different, you might want to change one of the two.
Chao Xu
CC BY-SA 4.0
2019-10-14T22:49:24.277Z
Yeah sorry, initially I thought the problem reduces to that and then realized it is not so changed it.
HHH
CC BY-SA 4.0
2019-10-16T04:07:00.667Z
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
<graph-theory><graph-colouring><combinatorics><constructive-mathematics>
conversion to DAG
HHH
# conversion to DAG

(Asked by: username_0 on 2019-10-13)

Can we reverse directions instead?

**Tags:** graph-theory, graph-colouring, combinatorics, constructive-mathematics
> **Comments:**
> **username_1**: The title and the description are very different, you might want to change one of the two.  
> **username_0**: Yeah sorry, initially I thought the problem reduces to that and then realized it is not so changed it.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2019-10-13. Score: 6

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

> **Comments:**
> **username_0**: No it is not, a feedback arc set removes edges, whereas here we are only allowed to flip edges.  
> **username_4**: The minimum set to remove and the minimum set to flip are identical to each other.  
> **username_0**: 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.  
> **username_5**: 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$.  
> **username_0**: Thanks man, you are right.  

---

