论文标题
挖掘和锦标赛的不可逆转性
Invertibility of digraphs and tournaments
论文作者
论文摘要
对于定向的图形$ d $和一套$ x \ subseteq v（d）$，$ d $中的$ x $的反转是通过逆转$ d $的边缘的方向而获得的，而$ d $ in $ x $中的digraph。 $ d $，$ \ textrm {inv}（d）$的反转数是最小反转数，可以依次应用于$ d $，以产生一个无环的挖掘。回答最近的一个问题，即bang-jensen，da Silva和Havet，我们表明，对于每个$ k \ in \ mathbb {n} $和toram $ t $，确定$ \ \ textrm {invt}（t）\ leq k $是否可以解决时间$ o_k（| o_k（| v（t）$ k $，特别是，当通过$ k $参数化时，问题是固定参数。另一方面，我们以他们的工作为基础，以证明他们的猜想是，对于$ k \ geq 1 $，确定是否具有$ \ textrm {inv}（d）\ leq k $是NP-Complete的问题。我们还构造了以反转数量等于其周期横向数的两倍的构造图形，这证实了Bang-Jensen，da Silva和Havet的另一个猜想，我们为他们的猜想提供了一个反例，以证明其在某些情况下证明它具有所谓的“ Dijoin” digraphs的反转数。最后，在这种情况下，我们渐近地解决了自然的极端问题，从而改善了Belkhechine，Bouaziz，Bouaziz，Boudabbous和Pouzet的先前范围，以表明$ n $ vertex锦标赛的最大反演数为$（1+o（1+o（1））n $。
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$, $\textrm{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 $k\in\mathbb{N}$ and tournament $T$, the problem of deciding whether $\textrm{inv}(T)\leq k$ is solvable in time $O_k(|V(T)|^2)$, which is tight for all $k$. In particular, the problem is fixed-parameter tractable when parameterised by $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 $\textrm{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$.
