pith. sign in

arxiv: 2604.05528 · v1 · submitted 2026-04-07 · 💻 cs.DS

Parameterized algorithms for k-Inversion

Dhanyamol Antony , L. Sunil Chandran , Dalu Jacob , R.B. Sandeep This is my paper

Pith reviewed 2026-05-10 19:27 UTC · model grok-4.3

classification 💻 cs.DS
keywords k-Inversiondecycling familiesparameterized algorithmstreewidthblock graphstournamentsdirected graphsFPT
0
0 comments X

The pith

k-Inversion admits an FPT algorithm on block graphs and a treewidth-parameterized algorithm on general directed graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses the k-Inversion problem of deciding whether a directed graph can be made acyclic by inverting all arcs inside at most k vertex subsets. Earlier work proved the problem NP-complete for every fixed k and supplied an FPT algorithm only when the input is a tournament. The authors first extend that tournament algorithm to a broader variant of the problem. They then apply the extension to obtain an algorithm whose running time depends only on k when the underlying undirected graph is a block graph. For arbitrary directed graphs they give a second algorithm whose running time is 2 to the O of treewidth times (k plus treewidth) times a polynomial in the number of vertices.

Core claim

The paper presents a generalization of the existing FPT algorithm for k-Inversion on tournaments to a broader variant of the problem on tournaments. Using this generalization together with the block structure of the input graph, it obtains an FPT algorithm parameterized by k for k-Inversion on block graphs. It further supplies an algorithm that solves k-Inversion on general directed graphs in time 2^{O(tw(k + tw))} n^{O(1)}, where tw denotes the treewidth of the underlying undirected graph.

What carries the argument

The decycling family of at most k vertex subsets, whose existence is decided by generalizing inversion techniques from tournaments and combining them with block-graph decomposition and dynamic programming over tree decompositions.

Load-bearing premise

The generalization of the tournament algorithm to a broader variant is correct and combines with the block-graph structure to produce an FPT algorithm.

What would settle it

A concrete block-graph instance together with a small integer k on which the claimed FPT algorithm returns the wrong yes/no answer, or a general directed graph for which the observed running time exceeds 2^{O(tw(k + tw))} n^{O(1)}.

read the original abstract

Inversion of a directed graph $D$ with respect to a vertex subset $Y$ is the directed graph obtained from $D$ by reversing the direction of every arc whose endpoints both lie in $Y$. More generally, the inversion of $D$ with respect to a tuple $(Y_1, Y_2, \ldots, Y_\ell)$ of vertex subsets is defined as the directed graph obtained by successively applying inversions with respect to $Y_1, Y_2, \ldots, Y_\ell$. Such a tuple is called a \emph{decycling family} of $D$ if the resulting graph is acyclic. In the \textsc{$k$-Inversion} problem, the input consists of a directed graph $D$ and an integer $k$, and the task is to decide whether $D$ admits a decycling family of size at most $k$. Alon et al.\ (SIAM J.\ Discrete Math., 2024) proved that the problem is NP-complete for every fixed value of $k$, thereby ruling out XP algorithms, and presented a fixed-parameter tractable (FPT) algorithm parameterized by $k$ for tournament inputs. In this paper, we generalize their algorithm to a broader variant of the problem on tournaments and subsequently use this result to obtain an FPT algorithm for \textsc{$k$-Inversion} when the underlying undirected graph of the input is a block graph. Furthermore, we obtain an algorithm for \textsc{$k$-Inversion} on general directed graphs with running time $2^{O(\mathrm{tw}(k + \mathrm{tw}))} \cdot n^{O(1)}$, where $\mathrm{tw}$ denotes the treewidth of the underlying graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper defines inversion of a digraph D w.r.t. a vertex subset Y (reversing all arcs internal to Y) and extends it to a decycling family of at most k such subsets whose successive application yields an acyclic digraph. Building on Alon et al.'s FPT algorithm for tournaments, the authors generalize the approach to a broader tournament variant and combine it with the block-cut tree structure to obtain an FPT algorithm for k-Inversion when the underlying undirected graph is a block graph. They further give a treewidth-based algorithm for arbitrary digraphs with running time 2^{O(tw(k + tw))} n^{O(1)}.

Significance. If the claims hold, the results meaningfully extend the parameterized complexity of k-Inversion: they lift the tournament FPT result to the larger class of block graphs (which properly contains tournaments) while respecting the known NP-completeness for fixed k, and supply a natural treewidth parameterization whose exponent is consistent with a DP that tracks subset membership vectors together with local orientation and acyclicity information. The explicit running-time bound and the two-step reduction strategy constitute concrete, falsifiable contributions to the literature on inversion problems.

minor comments (4)
  1. §3 (generalization to broader tournament variant): the proof sketch of the generalized FPT algorithm should explicitly state the size of the DP table and the recurrence for updating the inversion count when extending a partial family; the current high-level description leaves the precise state space implicit.
  2. §4 (block-graph algorithm): the combination of the tournament subroutine with the block-cut tree is only outlined; a short paragraph clarifying how the decycling families on individual blocks are glued across cut vertices would improve readability.
  3. §5 (treewidth DP): the auxiliary state for orientation parities and acyclicity checks on bags is mentioned but not enumerated; listing the O(tw^2) components explicitly would make the 2^{O(tw(k+tw))} bound easier to verify.
  4. Throughout: several citations to Alon et al. (2024) appear without page or theorem numbers; adding precise references would help readers locate the base tournament algorithm.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending minor revision. The provided summary accurately reflects the paper's contributions, including the generalization from tournaments to block graphs and the treewidth-based algorithm for general digraphs. Since the report lists no major comments, we have no point-by-point rebuttals to offer here. We will address any minor issues in the revised version.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's derivation relies on generalizing an external FPT algorithm from Alon et al. for tournaments and combining it with standard block-cut tree techniques for block graphs, plus an independent treewidth DP for general graphs. No self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations appear; the running time 2^{O(tw(k+tw))} n^{O(1)} follows directly from typical DP state tracking on bags without circular dependencies on the target result itself. The claims are self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph-theoretic facts about tree decompositions and block graphs. No new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard properties of tree decompositions and nice tree decompositions hold for the underlying undirected graph.
    Invoked implicitly when the algorithm is stated in terms of tw.
  • domain assumption Block graphs admit a tree-like structure that allows reduction to the tournament case.
    Used to obtain the FPT result for block graphs.

pith-pipeline@v0.9.0 · 5632 in / 1296 out tokens · 34503 ms · 2026-05-10T19:27:04.082657+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Alon, N., Powierski, E., Savery, M., Scott, A.D., Wilmer, E.: Invertibility of di- graphs and tournaments. SIAM J. Discret. Math.38(1), 327–347 (2024).https: //doi.org/10.1137/23M1547135

    work page doi:10.1137/23m1547135 2024

  2. [2]

    The Elec- tronic Journal of Combinatorics32(1) (2025).https://doi.org/10.37236/12983

    Aubian, G., Havet, F., Hörsch, F., Kingelhoefer, F., Nisse, N., Rambaud, C., Ver- mande, Q.: Problems, proofs, and disproofs on the inversion number. The Elec- tronic Journal of Combinatorics32(1) (2025).https://doi.org/10.37236/12983

    work page doi:10.37236/12983 2025

  3. [3]

    Bang-Jensen, F

    Bang-Jensen,J.,Havet,F.,Hörsch,F.,Rambaud,C.,Reinald,A.,Silva,C.:Making an oriented graph acyclic using inversions of bounded or prescribed size. arXiv preprintarXiv:2511.22562(2025).https://doi.org/10.48550/arXiv.2511.22562

    work page doi:10.48550/arxiv.2511.22562 2025

  4. [4]

    Bang-Jensen, J., da Silva, J.C.F., Havet, F.: On the inversion number of oriented graphs. Discret. Math. Theor. Comput. Sci.23(2) (2021).https://doi.org/10. 46298/DMTCS.7474

    work page 2021

  5. [5]

    Behague and P

    Behague, N., Gaudart-Wifling, P.: A case of the dijoin conjecture on inverting oriented graphs. arXiv preprint arXiv:2509.10232 (2025).https://doi.org/10. 48550/arXiv.2509.10232

    work page arXiv 2025

  6. [6]

    The Electronic Journal of Combinatorics32(1) (2025).https: //doi.org/10.37236/13018

    Behague, N., Johnston, T., Morrison, N., Ogden, S.: A note on inverting the dijoin of oriented graphs. The Electronic Journal of Combinatorics32(1) (2025).https: //doi.org/10.37236/13018

    work page doi:10.37236/13018 2025

  7. [7]

    Comptes Rendus

    Belkhechine, H., Bouaziz, M., Boudabbous, I., Pouzet, M.: Inversion dans les tournois. Comptes Rendus. Mathématique348(13-14), 703–707 (2010)

    work page 2010

  8. [8]

    Graphs Comb.37(3), 823–838 (2021).https: //doi.org/10.1007/S00373-021-02282-0

    Belkhechine, H., Salha, C.B.: Making a tournament indecomposable by one subtournament-reversal operation. Graphs Comb.37(3), 823–838 (2021).https: //doi.org/10.1007/S00373-021-02282-0

    work page doi:10.1007/s00373-021-02282-0 2021

  9. [9]

    Courcelle, B.: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput.85(1), 12–75 (1990).https://doi.org/10.1016/ 0890-5401(90)90043-H

    work page 1990

  10. [10]

    6 Josep Díaz, Olli Pottonen, Maria J

    Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015).https: //doi.org/10.1007/978-3-319-21275-3

    work page doi:10.1007/978-3-319-21275-3 2015

  11. [11]

    Journal of Graph Theory111(2), 31–62 (2026).https://doi.org/10.1002/jgt.23290

    Duron, J., Havet, F., Hörsch, F., Rambaud, C.: On the Minimum Number of Inver- sions to Make a Digraph k-(Arc-) Strong. Journal of Graph Theory111(2), 31–62 (2026).https://doi.org/10.1002/jgt.23290

    work page doi:10.1002/jgt.23290 2026

  12. [12]

    Diameter of the inversion graph.arXiv preprint, 2024.arXiv:2405.04119

    Havet, F., Hörsch, F., Rambaud, C.: Diameter of the inversion graph. arXiv preprintarXiv:2405.04119(2024).https://doi.org/10.48550/arXiv.2405.04119

    work page doi:10.48550/arxiv.2405.04119 2024

  13. [13]

    Korhonen, A single-exponential time 2-approximation algorithm for treewidth, in: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), 2022, pp

    Korhonen, T.: A single-exponential time 2-approximation algorithm for treewidth. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. pp. 184–192. IEEE (2021).https: //doi.org/10.1109/FOCS52979.2021.00026

    work page doi:10.1109/focs52979.2021.00026 2021

  14. [14]

    arXiv preprint arXiv:2404.14937 (2024).https://doi.org/10.48550/ arXiv.2404.14937

    Wang, H., Yang, Y., Lu, M.: The inversion number of dijoins and blow-up digraphs. arXiv preprint arXiv:2404.14937 (2024).https://doi.org/10.48550/ arXiv.2404.14937

    work page arXiv 2024

  15. [15]

    Journal of Graph Theory110(1), 82–91 (2025).https://doi.org/10.1002/JGT.23251

    Yuster, R.: On Tournament Inversion. Journal of Graph Theory110(1), 82–91 (2025).https://doi.org/10.1002/JGT.23251

    work page doi:10.1002/jgt.23251 2025