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.

In 1982, Berge defined the class of α-diperfect digraphs. A digraph D is α-diperfect if every induced subdigraph H of D satisfies the following property: for every maximum stable set S of H there is a path partition P of H in which every P ε P contains exactly one vertex of S. Berge conjectured a characterization of α-diperfect digraphs by forbidding induced orientations of odd cycles. In 2023, de Paula Silva, Nunes da Silva and Lee presented an infinite family of counterexamples for Berge’s Conjecture. These digraphs, namely D→ 2t+1 , are acyclic and have stability number two. In this paper, we prove that an acyclic digraph D with stability number two is α-diperfect if and only if D does not contain a D→ 2t+1 as an induced subdigraph.

In 1982, Berge defined the class of χ-diperfect digraphs. A digraph D is χ-diperfect if for every minimum coloring S of D there is a path P containing exactly one vertex of each color class of S and this property holds for every induced subdigraph of D. The ultimate goal in this research area is to obtain a characterization of χ-diperfect digraphs in terms of forbidden induced subdigraphs, but this may be a very difficult problem and not likely to be solved in a near future. Berge showed the first examples of obstructions for χ-diperfect digraphs (i.e. minimal non-χ-diperfect digraphs) by presenting orientations of odd cycles and complements of odd cycles that are not χ-diperfect. In 2022, de Paula Silva, Nunes da Silva and Lee showed characterizations of non-χ-diperfect super-orientations of odd cycles and their complements. Moreover, they showed that these structures are not the only obstructions for χ-diperfect digraphs, by presenting new obstructions with stability number two and three. In this paper, we present new obstructions for χ-diperfect digraphs with arbitrary stability number and arbitrary chromatic number.