On the inversion number of oriented graphs

Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by $\mathrm{i}\mathrm{n}\mathrm{v}(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $\tau (D)$, ${\tau }^{\mathrm{\prime }}(D)$, and $\nu (D)$ the cycle transversal number, the cycle arc-transversal number and the cycle packing number of $D$ respectively, one shows that ${\rm inv}(D) \leq \tau’ (D)$,${\rm inv}(D) \leq 2\tau(D)$andthereexistsafunction$g$ such that $\mathrm{i}\mathrm{n}\mathrm{v}(D)\le g(\nu (D))$. We conjecture that for any two oriented graphs $L$ and $R$, $\mathrm{i}\mathrm{n}\mathrm{v}(L\to R)=\mathrm{i}\mathrm{n}\mathrm{v}(L)+\mathrm{i}\mathrm{n}\mathrm{v}(R)$ where $L\to R$ is the dijoin of $L$ and $R$. This would imply that the first two inequalities are tight. We prove this conjecture when ${\rm inv}(L)\leq 1$and${\rm inv}®\leq 2$andwhen${\rm inv}(L) ={\rm inv}®=2$and$L$and$R$arestronglyconnected\mathrm{.}Wealsoshowthatthefunction$g$ of the third inequality satisfies $g(1)\le 4$. We then consider the complexity of deciding whether $\mathrm{i}\mathrm{n}\mathrm{v}(D)\le k$ for a given oriented graph $D$. We show that it is NP-complete for $k=1$, which together with the above conjecture would imply that it is NP-complete for every $k$. This contrasts with a result of Belkhechine et al. which states that deciding whether $\mathrm{i}\mathrm{n}\mathrm{v}(T)\le k$ for a given tournament $T$ is polynomial-time solvable.