3
$\begingroup$

I have the following problem: let $G$ be a finite directed graph with $V$ vertices $v_i$ and $E$ (directed) edges $e_j$. I know that if an edge $e_k = (v_i, v_j)$ is in the graph, then the opposite edge $-e_k = (v_j, v_i)$ is not in the graph. I also know that the graph contains at least one cycle. My goal is to render the graph acyclic by swapping the direction of some edges pertaining to at least one cycle.

I figured this was simple induction reasoning, i.e. swap an edge in any given cycle thus removing it, and repeat. But I cannot find a proof that it is possible to pick an edge which would not create a new cycle when swapped, nor can I find a counter-example with a finite graph.

The lemma I'd like to prove would be: given a graph $G$ such as above, there exists edge $(v_i, v_j)$ in one of the cycles so that replacing it with its opposite $(v_j, v_i)$ decreases the number of cycles in $G$ by at least 1. However, I couldn't find anything related... Any idea?

Thanks for your help

$\endgroup$
6
$\begingroup$

This is closely related to a standard (NP-complete) optimization problem, the minimum feedback edge set. Normally, this problem is defined as asking for the minimum set of edges $F$ to remove from a digraph $G$ to make $G-F$ acyclic. However, reversing the same set of edges $(G-F+F^R)$ also gives a DAG.

To see this, first note that each removed edge $f_i$ must be part of a cycle $C_i$ in $G-F+f_i$, or else the set of removed edges would not be minimal. But then if there were a cycle in $G-F+F^R$, you could replace each edge $f_i^R$ in this cycle by the corresponding path in $C_i-f_i$ and get a cycle in $G-F$.

The same argument works whenever $F$ is minimal, not just minimum. This might be helpful if you actually want to construct a set $F$, since it means you can do so without having to solve an NP-hard problem.

So this doesn't exactly give you a sequence of edges whose individual reversals decrease the number of cycles monotonically, but it does give you a set of edges that all participate in cycles and whose joint reversal eliminates all cycles.

$\endgroup$

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.