2026-07-21T12:29:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26173 2026-07-02T07:14:09Z ddc:004 open_access

Making an Oriented Graph Acyclic Using Inversions of Bounded or Prescribed Size Bang-Jensen, Jørgen Havet, Frédéric Hörsch, Florian Rambaud, Clément Reinald, Amadeus Silva, Caroline digraph inversion orientation NP-hardness acyclic reconfiguration 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. (⩽ 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, whenever p ≠ n-1, we construct a polynomial-time algorithm deciding (= p)-invertibility. We then consider the (= p)-inversion number, inv^{= p}(D) (resp. (⩽ p)-inversion number, inv^{⩽ p}(D)), defined as the minimum number of (= p)-inversions (resp. (⩽ p)-inversions) rendering D acyclic. We show that every (= p)-invertible digraph D satisfies inv^{= p}(D) ⩽ |A(D)| for every integer p ⩾ 2. When p is even, we moreover bound 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 (⩽ p)-inversion number, of a given oriented graph is at most a given integer k. For any fixed positive integer p ⩾ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jørgen Bang-Jensen and Frédéric Havet and Florian Hörsch and Clément Rambaud and Amadeus Reinald and Caroline Silva 2026 Is Part Of LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WG.2026.7 urn:nbn:de:0030-drops-261733 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode