{"ID":2836039,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.22562","arxiv_id":"2511.22562","title":"Making an oriented graph acyclic using inversions of bounded or prescribed size","abstract":"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.","short_abstract":"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)$-invert...","url_abs":"https://arxiv.org/abs/2511.22562","url_pdf":"https://arxiv.org/pdf/2511.22562v1","authors":"[\"Jørgen Bang-Jensen\",\"Frédéric Havet\",\"Florian Hörsch\",\"Clément Rambaud\",\"Amadeus Reinald\",\"Caroline Silva\"]","published":"2025-11-27T15:51:42Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}