On the minimum number of inversions to make a digraph $k$-(arc-)strong

Abstract

The {\it inversion} of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D⟨X⟩$. We study $sin{v}_k^{\prime }(D)$ (resp. $sin{v}_k(D)$) which is the minimum number of inversions needed to transform $D$ into a $k$-arc-strong (resp. $k$-strong) digraph and $sinv'_k(n) = \max\{sinv'_k(D) \mid D~\mbox{is a $2k$-edge-connecteddigraphoforder$n$}\}$. We show : $(i):\frac{1}{2}\log (n-k+1)\le sin{v}_k^{\prime }(n)\le \log n+4k-3$ ; $(ii):$ for any fixed positive integers $k$ and $t$, deciding whether a given oriented graph $D$ with $sin{v}_k^{\prime }(D)<+\infty$ satisfies $sin{v}_k^{\prime }(D)\le t$ is NP-complete; $(iii):$ for any fixed positive integers $k$ and $t$, deciding whether a given oriented graph $D$ with $sin{v}_k(D)<+\infty$ satisfies $sin{v}_k(D)\le t$ is NP-complete; $(iv):$ if $T$ is a tournament of order at least $2k+1$, then $sin{v}_k^{\prime }(T)\le sin{v}_k(T)\le 2k$, and $sin{v}_k^{\prime }(T)\le \frac{4}{3}k+o(k)$; $(v):\frac{1}{2}\log (2k+1)\le sin{v}_k^{\prime }(T)\le sin{v}_k(T)$ for some tournament $T$ of order $2k+1$; $(vi):$ if $T$ is a tournament of order at least $19k-2$ (resp. $11k-2$), then $sin{v}_k^{\prime }(T)\le sin{v}_k(T)\le 1$ (resp. $sin{v}_k(T)\le 3$); $(vii):$ for every $\epsilon >0$, there exists $C$ such that $sin{v}_k^{\prime }(T)\le sin{v}_k(T)\le C$ for every tournament $T$ on at least $2k+1+\epsilon k$ vertices.