What is the complexity of this problem


Input: a directed graph $G(V,A)$ and an integer $k$

Output: YES if $k$ arc reversals are enough to transform $G$ into an Eulerian graph, otherwise NO

Given an arc $(u,v)\in A$, an act of reversing it will result in the opposite arc $(v,u)$ while the original arc $(u,v)$ will disappear as well.

There are related meta-results on node and edge deletions by Yannakakis. So, I wonder what we can do if the actions are changed from deletion to reversals.

If instead of using Eulerian property, we use Hamiltonian property then we immediately get an NP-complete problem by setting $k=0$.

  • $\begingroup$ yes, arc is just directed edge. The terms are interchangeable. $\endgroup$ Nov 27 '18 at 12:56
  • $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – Raphael
    Nov 27 '18 at 20:33

This problem can be solved in polynomial time.

For such a graph $G=(V,A)$, turn it into a new weighted undirected graph $G'$ as follows, where we denote respectively by $d^{\mathrm{in}}(v)$ and $d^{\mathrm{out}}(v)$ the in-degree and out-degree of $v$.

For every $v$, we have that $d^{\mathrm{in}}(v)- d^{\mathrm{out}}(v)$ is even. Otherwise, the graph cannot be changed to an Eulerian graph.

  1. For each edge $(u,v)\in A$, construct two vertices $u_{\rightarrow v}, v_{u\rightarrow}$ and an edge with weight $1$ between them.

  2. For each vertex $v\in V$, add an edge with weight $1+\epsilon$ (where $\epsilon$ is a small positive number that depends on the size of the graph) between $v_{u_1\rightarrow}$ and $v_{\rightarrow u_2}$ for all $u_1,u_2\in V$ such that $(u_1,v),(v,u_2)\in A$.

  3. For each vertex $v\in V$, construct $\left|d^{\mathrm{in}}(v)- d^{\mathrm{out}}(v) \right|/2$ vertices $v_1,v_2,\ldots$. If $d^{\mathrm{in}}(v)\ge d^{\mathrm{out}}(v)$, add an edge with weight $1$ between $v_i$ and $v_{u\rightarrow}$ for all $i$ and $u\in V$ such that $(u,v)\in A$. Otherwise, add an edge with weight $1$ between $v_i$ and $v_{\rightarrow u}$ for all $i$ and $u\in V$ such that $(v,u)\in A$.

Recall that a directed graph is Eulerian iff each vertex has equal in-degree and out-degree, assuming the underlying undirected graph is connected. Now we can see finding a minimum number of edges to reverse in $G$ is equivalent to finding a maximum weight matching in $G'$, by reversing all edges $(u,v)$ such that $u_{\rightarrow v}$ is matched with $v_{u\rightarrow }$ in the maximum matching.

  • $\begingroup$ have made some small edits to make your answer more consistent with my question. More comments on this soon. Tks for answering. $\endgroup$ Nov 28 '18 at 7:14
  • $\begingroup$ Why does a maximum weight matching have to exclude all the $v_i$'s vertices? $\endgroup$ Nov 28 '18 at 15:06
  • $\begingroup$ @ThinhD.Nguyen No, it doesn't. A maximum weight matching here must be a perfect matching. $\endgroup$
    – xskxzr
    Nov 28 '18 at 15:18
  • $\begingroup$ A concise proof of correctness would be necessary for this. Could you elaborate on one? $\endgroup$ Nov 29 '18 at 0:45
  • $\begingroup$ @ThinhD.Nguyen A strict proof is somewhat verbose so I don't want to write it. Roughly speaking, a maximum matching is a perfect matching where $d:=\left|d^{\mathrm{in}}(v)-d^{\mathrm{out}}(v)\right|/2$ $v_{u\rightarrow}$s (say $d^{\mathrm{in}}(v)>d^{\mathrm{out}}(v)$) are matched with $v_i$s, so the edges to be reversed whose end vertices are $v$ are $d$ more than those whose start vertices are $v$, which means after reversing, the in-degree of $v$ equals to the out-degree of $v$. $\endgroup$
    – xskxzr
    Nov 29 '18 at 4:58

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.