Given an oriented graph $D$, the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$. When the subset $X$ is of size $p$ (resp. at most $p$), this operation is called an $(=p)$-inversion (resp. $(\leq p)$-inversion). Then, an oriented graph is $(=p)$-invertible if it can be made acyclic by a sequence of $p$-inversions. We observe that, for $n=|V(D)|$, deciding whether $D$ is $(=n-1)$-invertible is equivalent to deciding whether $D$ is acyclically pushable, and thus NP-complete. In all other cases, when $p \neq n-1$, we construct a polynomial-time algorithm to decide $(=p)$-invertibility. We then consider the $(= p)$-inversion number, $\text{inv}^{= p}(D)$ (resp. $(\leq p)$-inversion number, $\text{inv}^{\leq p}(D)$), defined as the minimum number of $(=p)$-inversions (resp. $(\leq p)$-inversions) rendering $D$ acyclic. We show that every $(=p)$-invertible digraph $D$ satisfies $\text{inv}^{= p}(D) \leq |A(D)|$ for every integer $p\geq 2$. When $p$ is even, we bound $\text{inv}^{= p}$ by a (linear) function of the feedback arc set number, and rule out the existence of any bounding function for odd $p$. Finally, we study the complexity of deciding whether the $(= p)$-inversion number, or the $(\leq p)$-inversion number, of a given oriented graph is at most a given integer $k$. For any fixed positive integer $p \geq 2$, when $k$ is part of the input, we show that both problems are NP-hard even in tournaments. In general oriented graphs, we prove $W[1]$-hardness for both problems when parameterized by $p$, even for $k=1$. In contrast, we exhibit polynomial kernels in $p + k$ for both problems in tournaments.

翻译：给定一个有向图$D$，对顶点子集$X$进行反转操作是指将所有两个端点均在$X$中的弧的方向反转。当子集$X$的规模恰好为$p$（相应地，至多为$p$）时，该操作称为$(=p)$-反转（相应地，$(\leq p)$-反转）。若一个定向图能通过一系列$p$-反转操作变为无环图，则称其为$(=p)$-可反转的。我们观察到，对于$n=|V(D)|$，判定$D$是否为$(=n-1)$-可反转的等价于判定$D$是否可通过无环推演实现，因此该问题是NP完全的。在其他所有情况下，当$p \neq n-1$时，我们构建了一个多项式时间算法来判定$(=p)$-可反转性。接着我们考虑$(=p)$-反转数$\text{inv}^{= p}(D)$（相应地，$(\leq p)$-反转数$\text{inv}^{\leq p}(D)$），其定义为使$D$变为无环图所需的最小$(=p)$-反转（相应地，$(\leq p)$-反转）次数。我们证明：对于任意整数$p\geq 2$，每个$(=p)$-可反转的有向图$D$均满足$\text{inv}^{= p}(D) \leq |A(D)|$。当$p$为偶数时，我们通过反馈弧集数的（线性）函数界定了$\text{inv}^{= p}$的上界，并排除了奇数$p$存在任何界定函数的可能性。最后，我们研究了判定给定有向图的$(=p)$-反转数或$(\leq p)$-反转数是否不超过给定整数$k$的计算复杂度。对于任意固定的正整数$p \geq 2$，当$k$作为输入的一部分时，我们证明即使在锦标赛中这两个问题都是NP困难的。在一般有向图中，我们证明了当以$p$为参数时，即使$k=1$，这两个问题都是$W[1]$困难的。相比之下，我们展示了在锦标赛中这两个问题在参数$p + k$下存在多项式核。