Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one
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.


For each edge $(u,v)\in A$, construct two vertices $u_{\rightarrow v}, v_{u\rightarrow}$ and an edge with weight $1$ between them.
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$.
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.