On the inversion number of oriented graphs

DOI10.46298/DMTCS.7474arXiv2105.04137MaRDI QIDQ6507574FDOQ6507574

Authors: Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, Frédéric Havet 

Abstract: 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 $minv(D)$, is the minimum number of inversions needed to make $D$ acyclic. Denoting by $au(D)$, $a{u}^{\prime }(D)$, and $u(D)$ the cycle transversal number, the cycle arc-transversal number and the cycle packing number of $D$ respectively, one shows that $minv(D)leqa{u}^{\prime }(D)$, $minv(D)leq2au(D)$ and there exists a function $g$ such that $minv(D)leqg(u(D))$. We conjecture that for any two oriented graphs $L$ and $R$, $minv(LightarrowR)=minv(L)+minv(R)$ where $LightarrowR$ is the dijoin of $L$ and $R$. This would imply that the first two inequalities are tight. We prove this conjecture when $minv(L)leq1$ and $minv(R)leq2$ and when $minv(L)=minv(R)=2$ and $L$ and $R$ are strongly connected. We also show that the function $g$ of the third inequality satisfies $g(1)leq4$. We then consider the complexity of deciding whether $minv(D)leqk$ 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 $minv(T)leqk$ for a given tournament $T$ is polynomial-time solvable.

This page was built for publication: On the inversion number of oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507574)