pith. sign in

arxiv: 2604.22584 · v1 · submitted 2026-04-24 · 🧮 math.CO · cs.DM

Increasing arc-connectivity by bounded- and fixed-size inversions

Florian H\"orsch , Lucas Picasarri-Arrieta This is my paper

Pith reviewed 2026-05-08 10:55 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords arc-connectivitydigraph inversionk-arc-strongapproximation algorithmNP-hardnessparameterized complexitydirected graphsconnectivity augmentation
0
0 comments X

The pith

Sufficiently large digraphs can be made k-arc-strong by inversions of exactly p vertices, and a (4k-2+ε) approximation finds near-minimal bounded inversions.

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

The paper characterizes the digraphs that become k-arc-strong after a sequence of inversions each flipping exactly p vertices, when the digraph is large enough. It also supplies a polynomial-time algorithm that approximates the smallest number of inversions of size at most p needed to reach the same connectivity level. This matters because it shows how local arc reversals inside vertex subsets can replace the addition of new arcs to strengthen directed networks. The results include matching hardness proofs that exact minimization is NP-hard and APX-hard, plus parameterized hardness for small numbers of inversions.

Core claim

For all integers p ≥ 2 and k ≥ 1, the digraphs that can be made k-arc-strong by applying inversions of size exactly p are characterized, provided they are sufficiently large. For p ≥ 3 and k ≥ 1 and any ε > 0, there exists a polynomial-time (4k-2+ε)-approximation algorithm for the minimum number of inversions of size at most p that make a given digraph k-arc-strong. The problem is NP-hard and APX-hard; it is also W[1]-hard with respect to p for deciding whether one inversion of size at most p suffices, and W[1]-hard with respect to the number of size-2 inversions needed to reach 2-arc-strength.

What carries the argument

The inversion of a vertex subset X, which reverses every arc with both endpoints inside X, used as the sole operation to increase the minimum number of arcs leaving any nonempty proper subset of vertices.

If this is right

  • Any digraph meeting the characterization can be made k-arc-strong by a finite sequence of exactly p-sized inversions.
  • The approximation algorithm produces a collection of at most p-sized inversions whose size is at most (4k-2+ε) times the smallest possible collection that achieves k-arc-strength.
  • No polynomial-time algorithm for computing the exact minimum number of bounded inversions exists unless P=NP.
  • No fixed-parameter tractable algorithm exists for deciding single-inversion feasibility when parameterized by the inversion size p, unless FPT=W[1].

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same inversion operation could be studied for vertex-connectivity or for making digraphs Eulerian.
  • In applications such as transportation or communication networks, bounded inversions correspond to low-cost local rewiring that avoids adding physical links.
  • The approximation factor 4k-2+ε may be improvable for fixed small k, or shown tight by a matching lower bound construction.
  • The characterization technique may extend to other bounded local operations that preserve the underlying undirected graph.

Load-bearing premise

The digraphs under study are assumed to be sufficiently large so that the characterization for exactly p-sized inversions holds without small exceptional cases.

What would settle it

A concrete large digraph that satisfies every condition listed in the characterization yet cannot be made k-arc-strong by any collection of p-inversions, or a concrete input where the approximation algorithm returns a solution more than (4k-2+ε) times larger than the true minimum.

Figures

Figures reproduced from arXiv: 2604.22584 by Florian H\"orsch, Lucas Picasarri-Arrieta.

Figure 1
Figure 1. Figure 1: Two examples of k-obstructions, with k = 1 (left) and k = 3 (right). In both cases, each colour illustrates a part of the partition (X1, . . . , Xr, Y ), the vertices of Y being in red. multidigraph. Moreover, when it comes to feasibility, inversions of size 2 are exactly as powerful as arbitrary inversions. Interestingly, we can obtain the following result as a simple corollary of a result of Hörsch and S… view at source ↗
Figure 2
Figure 2. Figure 2: An example of a digraph where the number of necessary view at source ↗
Figure 3
Figure 3. Figure 3: The partition of V into (U0, U1, U2, {u}, W0, W1, W2, {w}). The dashed vertical line illustrates the partition (U, W). The sets X and Y contain the blue and red vertices, respectively. Between a vertex and a set of vertices, a solid line illustrates that all possible edges are present and a dotted line that none are present. Observe that u dominates U0 and w dominates W0, for otherwise there exists some ve… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the construction of D (right) from a graph G (left). Here, r = 3 and H is the complete graph K3. Note that, for the sake of better readability, we chose here a graph G that is not an instance of NPSI. Each grey square illustrates a copy of T. For better readability, we put two copies of Te, but these are the same one copy of T. Red, blue, and green arcs illustrate that there exist respec… view at source ↗
Figure 5
Figure 5. Figure 5: An example for the construction of a colour gadget. An instance view at source ↗
Figure 6
Figure 6. Figure 6: An example of the construction of D for the example depicted in view at source ↗
read the original abstract

For a digraph $D$ and some $X \subseteq V(D)$, the inversion of $X$ is the operation of flipping all arcs both of whose endvertices are in $X$. We initiate the study of establishing arc-connectivity properties by applying inversions of bounded or fixed size. For fixed-size inversions, the feasibility problem is interesting. For all integers $p \geq 2$ and $k \geq 1$, we give a characterization of the digraphs that can be made $k$-arc-strong by applying inversions of size exactly $p$, provided they are sufficiently large. For bounded-size inversions, the feasibility problem is easy, so we focus on minimising the number of inversions. We prove that for all integers $p\geq 3$ and $k \geq 1$ and any $\epsilon>0$, there exists a polynomial-time $(4k-2+\epsilon)$-approximation algorithm for computing the minimum number of inversions of size at most $p$ that make a given digraph $k$-arc-strong. This is in stark contrast to other results on inversion optimization problems. On the other hand, we show that for any $p\geq 3$ and $k \geq 1$ the problem is NP-hard, and, moreover, APX-hard. As a result on parameterized complexity, we show that for any $k \geq 2$, it is $W[1]$-hard with respect to $p$ to decide whether a given digraph can be made $k$-arc-strong by applying a single inversion of size at most $p$. We also prove that for a given multidigraph, it is $W[1]$-hard with respect to $\ell$ to decide whether it can be made 2-arc-strong by applying $\ell$ inversions of size 2.

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 / 3 minor

Summary. The paper studies augmenting the arc-connectivity of digraphs via inversions (reversing all arcs within a vertex subset) of exact size p or at most p. For all p ≥ 2 and k ≥ 1 it characterizes the digraphs that become k-arc-strong after exactly p inversions of size p, provided the digraph is sufficiently large. For p ≥ 3 it gives a polynomial-time (4k-2 + ε)-approximation algorithm for the minimum number of ≤p-sized inversions needed to make a digraph k-arc-strong, proves NP-hardness and APX-hardness of the minimization problem, and establishes W[1]-hardness for the parameterized versions (single inversion of size ≤p for k ≥ 2, and ℓ inversions of size 2 for 2-arc-strongness).

Significance. If the characterization and approximation hold, the contribution is notable: it supplies the first explicit structural description for fixed-size inversion augmentation and an approximation factor linear in k that is independent of p, in contrast to other inversion problems that lack constant-factor approximations. The separation between feasibility (easy for bounded size) and minimization (hard but approximable) plus the parameterized results delineate the complexity landscape cleanly. The work is grounded in standard digraph definitions and supplies both extremal and algorithmic results.

minor comments (3)
  1. The phrase 'sufficiently large' in the characterization theorem should be replaced by an explicit lower bound on |V| (or |V| in terms of p and k) in the statement of the theorem and in the abstract.
  2. Notation for the inversion operation and for k-arc-strongness should be introduced once in a preliminary section and then used consistently; a reference to a standard text (e.g., Bang-Jensen & Gutin) for basic arc-connectivity facts would help readers.
  3. The approximation algorithm is stated for any ε > 0; the dependence of the running time on ε should be made explicit (e.g., whether it is polynomial for fixed ε or involves 1/ε factors).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work, as well as the recommendation for minor revision. The report correctly highlights the characterization for exact-size inversions, the approximation algorithm and hardness results for bounded-size inversions, and the parameterized complexity findings. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes a characterization of sufficiently large digraphs that become k-arc-strong after exactly p fixed-size inversions, plus a (4k-2+ε)-approximation algorithm for the minimum number of ≤p inversions needed to reach k-arc-strong connectivity. Both results rest on standard definitions of digraphs, arc-connectivity, and the inversion operation (reversing all arcs internal to a vertex subset X). No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the proofs and algorithms are independent of the target quantities and rely on external graph-theoretic machinery rather than renaming or re-deriving their own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the work operates entirely within standard directed-graph theory and introduces no free parameters, ad-hoc axioms, or new entities beyond the input parameters p and k.

axioms (1)
  • standard math Standard definitions and properties of finite digraphs and arc-connectivity from combinatorial graph theory.
    The paper assumes the usual notions of directed graphs, arcs, and k-arc-strong connectivity without stating additional restrictions.

pith-pipeline@v0.9.0 · 5653 in / 1403 out tokens · 42049 ms · 2026-05-08T10:55:04.760991+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

37 extracted references · 37 canonical work pages · 2 internal anchors

  1. [1]

    N. Alon. Ranking tournaments.SIAM Journal on Discrete Mathematics, 20(1):137–142, 2006

    work page 2006

  2. [2]

    N. Alon, E. Powierski, M. Savery, A. Scott, and E. Wilmer. Invertibility of digraphs and tournaments.SIAM Journal on Discrete Mathematics, 38(1):327–347, 2024

    work page 2024

  3. [3]

    Arana, T

    C. Arana, T. Bellitto, H. Buffière, Q. Chuet, T. Pierron, and A. Reinald. Inversion diameter and 2-edge-colored homomorphisms.Preprint arXiv:2602.24171, 2026

    work page arXiv 2026

  4. [4]

    Aubian, F

    G. Aubian, F. Havet, F. Hörsch, F. Klingelhoefer, N. Nisse, C. Rambaud, and Q. Ver- mande. Problems, proofs, and disproofs on the inversion number.The Electronic Journal of Combinatorics, 32(1):#P1.42, 2025

    work page 2025

  5. [5]

    Bang-Jensen, J

    J. Bang-Jensen, J. C. F. da Silva, and F. Havet. On the inversion number of oriented graphs.Discrete Mathematics & Theoretical Computer Science, 23(2), 2022

    work page 2022

  6. [6]

    Bang-Jensen and G

    J. Bang-Jensen and G. Z. Gutin.Digraphs: Theory, Algorithms and Applications. Springer- Verlag, London, 2nd edition, 2009

    work page 2009

  7. [7]

    Bang-Jensen, F

    J. Bang-Jensen, F. Havet, F. Hörsch, C. Rambaud, A. Reinald, and C. Silva. Mak- ing an oriented graph acyclic using inversions of bounded or prescribed size.Preprint arXiv:2511.22562, 2025

    work page arXiv 2025

  8. [8]

    Behague and P

    N. Behague and P. Gaudart-Wifling. A case of the dijoin conjecture on inverting oriented graphs.Preprint arXiv:2509.10232, 2025

    work page arXiv 2025

  9. [9]

    Behague, T

    N. Behague, T. Johnston, N. Morrison, and S. Ogden. A note on inverting the dijoin of oriented graphs.The Electronic Journal of Combinatorics, 32(1):#P1.44, 2025

    work page 2025

  10. [10]

    Belkhechine, M

    H. Belkhechine, M. Bouaziz, I. Boudabbous, and M. Pouzet. Inversion dans les tournois. Comptes Rendus Mathematique, 348(13):703–707, 2010

    work page 2010

  11. [11]

    Charbit, S

    P. Charbit, S. Thomassé, and A. Yeo. The minimum feedback arc set problem is np-hard for tournaments.Combinatorics, Probability, and Computing, 16(1):1–4, 2007

    work page 2007

  12. [12]

    Chlebík and J

    M. Chlebík and J. Chlebíková. Complexity of approximating bounded variants of optimiza- tion problems.Theoretical Computer Science, 354(3):320–338, 2006

    work page 2006

  13. [13]

    Nombred’arcsdanslesgraphesk-arc-fortementconnexesminimaux.Compte- Rendu de l’Académie des Sciences de Paris A, 285(5):341–344, 1977

    M.Dalmazzo. Nombred’arcsdanslesgraphesk-arc-fortementconnexesminimaux.Compte- Rendu de l’Académie des Sciences de Paris A, 285(5):341–344, 1977

    work page 1977

  14. [14]

    Diestel.Graph Theory

    R. Diestel.Graph Theory. Graduate texts in mathematics. Springer, Berlin, Germany, 5th edition, 2017

    work page 2017

  15. [15]

    Duron, F

    J. Duron, F. Havet, F. Hörsch, and C. Rambaud. On the minimum number of inversions to make a digraphk-(arc-)strong.Journal of Graph Theory, 111(2):31–62, 2026

    work page 2026

  16. [16]

    J. Edmonds. Edge-disjoint branchings. In R. Rustin, editor,Combinatorial Algorithms, pages 91–96. Academic Press, 1973

    work page 1973

  17. [17]

    A. Frank. An algorithm for submodular functions on graphs. In A. Bachem, M. Grötschel, and B. Korte, editors,Bonn Workshop on Combinatorial Optimization, volume 66 ofNorth- Holland Mathematics Studies, pages 97–120. North-Holland, 1982. 48

    work page 1982

  18. [18]

    A. Frank. An algorithm for submodular functions on graphs. InNorth-Holland Mathematics Studies, volume 66, pages 97–120. Elsevier, 1982

    work page 1982

  19. [19]

    Guruswami, J

    V. Guruswami, J. Håstad, R. Manokaran, P. Raghavendra, and M. Charikar. Beating the random ordering is hard: every ordering CSP is approximation resistant.SIAM Journal on Computing, 40(3):878–914, 2011

    work page 2011

  20. [20]

    Guruswami and E

    V. Guruswami and E. Lee. Simple proof of hardness of feedback vertex set.Theory of Computing, 12(6):1–11, 2016

    work page 2016

  21. [21]

    Havet, F

    F. Havet, F. Hörsch, and C. Rambaud. Diameter of the inversion graph.Innovations in Graph Theory, 3:49–88, 2026

    work page 2026

  22. [22]

    On the $(\leq p)$-inversion diameter of oriented graphs

    F. Havet, C. Rambaud, and C. Silva. On the(⩽p)-inversion diameter of oriented graphs. Preprint arXiv:2604.04633, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  23. [23]

    Hörsch and Z

    F. Hörsch and Z. Szigeti. Connectivity of orientations of 3-edge-connected graphs.European Journal of Combinatorics, 94:103292, 2021

    work page 2021

  24. [24]

    B. Jackson. Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs.Journal of Graph Theory, 12(3):429–436, 1988

    work page 1988

  25. [25]

    R. M. Karp.Reducibility among combinatorial problems. Springer, 2010

    work page 2010

  26. [26]

    W. F. Klostermeyer. Pushing vertices and orienting edges.Ars Combinatoria, 51:65–75, 1999

    work page 1999

  27. [27]

    W. Mader. Minimale n-fach kantenzusammenhängende graphen.Mathematische Annalen, 191(1):21–28, 1971

    work page 1971

  28. [28]

    D. Marx. Can you beat treewidth?Theory of Computing, 6(5):85–112, 2010

    work page 2010

  29. [29]

    Monnot and S

    J. Monnot and S. Toulouse. The path partition problem and related problems in bipartite graphs.Operations Research Letters, 35(5):677–684, 2007

    work page 2007

  30. [30]

    C. S. J. Nash-Williams. On orientations, connectivity and odd-vertex-pairings in finite graphs.Canadian Journal of Mathematics, 12:555–567, 1960

    work page 1960

  31. [31]

    Nishimura

    N. Nishimura. Introduction to reconfiguration.Algorithms, 11(4), 2018

    work page 2018

  32. [32]

    F. P. Ramsey. On a problem of formal logic.Proceedings of the London Mathematical Society, s2-30(1):264–286, 1930

    work page 1930

  33. [33]

    Schrijver.Combinatorial Optimization

    A. Schrijver.Combinatorial Optimization. Algorithms and Combinatorics. Springer, Berlin, Germany, 2003 edition, 2002

    work page 2003

  34. [34]

    Svensson

    O. Svensson. Hardness of vertex deletion and project scheduling.Theory of Computing, 9(24):759–781, 2013

    work page 2013

  35. [35]

    H. Wang, Y. Yang, and M. Lu. The inversion number of dijoins and blow-up digraphs. Preprint arXiv:2404.14937, 2024

    work page arXiv 2024

  36. [36]

    Y. Wang, H. Wang, Y. Yang, and M. Lu. Inversion diameter and treewidth.Preprint arXiv:2407.15384, 2024

    work page internal anchor Pith review arXiv 2024

  37. [37]

    R. Yuster. On tournament inversion.Journal of Graph Theory, 110(1):82–91, 2025. 49

    work page 2025