For an oriented graph $D$ and a set $X\subseteq V(D)$, the inversion of $X$ in $D$ is the digraph obtained by reversing the orientations of the edges of $D$ with both endpoints in $X$. The inversion number of $D$, $\operatorname{inv}(D)$, is the minimum number of inversions which can be applied in turn to $D$ to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet, we show that for each fixed $k\in\mathbb{N}$ the problem of deciding whether a tournament $T$ has $\operatorname{inv}(T)\leq k$ is solvable in time $O(\lvert V(T)\rvert ^2)$. This exponent is optimal for all $k$. On the other hand, we build on their work to prove their conjecture that for $k\geq 1$ the problem of deciding whether a general oriented graph $D$ has $\operatorname{inv}(D)\leq k$ is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called 'dijoin' digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an $n$-vertex tournament is $(1+o(1))n$.
翻译:方向图形 $D$和一套 $X\ subseteq V(D) 美元, 以美元为美元, 以美元反转 美元是翻转 $D$ 的边缘方向, 两个终点都以美元为美元。 $D$, $Otorname{inv} (D) 的反转数是美元( 美元) 的最低反转数, 可以转成美元, 以产生一个周期的分解。 回答最近 Bang- Jensen, da Silva 和 Hatt 的问题, 我们展示了每张固定的 $k\ in\ mathb{Nex$ 的偏向方向, 确定一个赛标是否$Operatorname{inv} (T)\leq k$, 在时间 $( lververV( T)\rvert%2) 中可以解析。 这个推算对于所有美元, 在另一面, 我们利用他们的工作来证明他们的预测: $G$(D$) 的比值, 显示一个直径 和直径的直径 。