Given any digraph $D$ is the flip distance to an acyclic reorientation of $D$ equal to the minimum cardinality of an acyclic feedback-set of $D$?

48 Views Asked by At

Given an arbitrary digraph $D=(V,A)$ we call any set $F\subseteq A$ a feedback-set of $D$ iff the digraph: $H=(V,A-F)$ is acyclic, while in particular we call $F\subseteq A$ an acyclic feedback-set of $D$ iff $F$ is a feedback-set of $D$ such that $H'=(V,F)$ is acyclic, likewise we let $\phi(D)$ be the minimum number of arcs in $D$ that if flipped will result in an acyclic digraph, or equivalently in symbols we let $\phi$ be the graph invariant such that $\phi(D)=\min\{|R\setminus A|:(V,R)\text{ is a reorientation of }D\}$ while moreover we write $\beta(D)=\min\{|F|:F\text{ is an acyclic feedback-set of }D\}$, now with all of that terminology established is it true that for every digraph $D$, we must have: $\beta(D)=\phi(D)$?

Clearly by definition $\beta(D)\leq\phi(D)$ because if flipping any set of arcs $A'\subseteq A$ in $D$ results in an acyclic digraph $H$ then we have that $(V,A-F)$ and $(V,F)$ are both subgraphs of $H$ thus these are both acyclic digraphs, thus $A'$ is an acyclic feedback-set of $D$ and thus $\beta(D)\leq |A'|$ where by definition we can choose the set of arcs we are flipping $A'\subseteq A$ in $D$ so that we have $|A'|=\phi(D)$ i.e. this means $\beta(D)\leq \phi(D)$. But is it true that $\phi(D)\leq \beta(D)$? I know this is true if $D$ is planar (i.e. this is true when $D$ is an orientation of a planar graph) but is this identity true in general?

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose that $F$ is a minimal feedback-set of $D$: the digraph $D-F$ is acyclic, but for every proper subset $F' \subset F$, the digraph $D - F'$ is not acyclic. Then I claim that the graph $D^{-F}$ produced by merely reversing all the arcs in $F$ is also acyclic.

This implies your second inequality and also implies that all minimal feedback-sets are acyclic, which was not obvious to me at first.


To see this, take any arc $(u,v) \in F$. Because $F' = F - \{(u,v)\}$ is not a feedback-set, there must be a cycle in $D - F'$; since this cycle is not in $D$, it must contain arc $(u,v)$. Deleting arc $(u,v)$ from this cycle still leaves a path from $v$ to $u$, which is a path in $D-F$.

Essentially, the existence of a $v$-to-$u$ path for every arc $(u,v) \in F$ means that the reverse arc $(v,u)$ would be redundant: it would not help create any cycles.

More formally, suppose that there is a cycle in $D^{-F}$. Every time that cycle uses an arc $(v,u)$ which is the reverse of an arc $(u,v) \in F$, replace that arc by the $v$-to-$u$ path in $D-F$. After we do this, we have obtained a closed walk in $D-F$, so there is a cycle in $D-F$: this contradicts our assumption that $F$ is a feedback-set.

Therefore $D^{-F}$ must be acyclic.