Inversion diameter and treewidth
Pith reviewed 2026-05-23 22:55 UTC · model grok-4.3
The pith
Graphs of treewidth k exist with inversion diameter exactly 2k, making the known upper bound tight, and all maximum-degree-3 graphs have inversion diameter at most 3.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
There exist graphs G of treewidth k with diam(I(G))=2k, and every graph G with maximum degree 3 satisfies diam(I(G))≤3. The first statement is shown by direct construction; the second follows from exhaustive verification that no degree-3 graph requires more than three inversions between any pair of orientations.
What carries the argument
The inversion graph I(G), whose vertices are the orientations of G and whose edges correspond to single inversions of a vertex subset.
If this is right
- The upper bound diam(I(G)) ≤ 2k for treewidth-k graphs is tight.
- The conjecture diam(I(G)) ≤ Δ holds for all graphs with Δ = 3.
- Inversion diameter is a well-defined parameter that separates treewidth from maximum degree in its worst-case growth.
Where Pith is reading between the lines
- The same constructions may be adaptable to show that other width parameters also admit linear inversion-diameter lower bounds.
- If the degree conjecture holds in general, inversion diameter would be bounded by a local parameter rather than a global one.
- The computer verification for degree 3 suggests that small-degree cases can be settled algorithmically even when analytic proofs are elusive.
Load-bearing premise
The explicit constructions have treewidth exactly k and force the inversion graph to have diameter exactly 2k, while the computer search correctly checks all degree-3 graphs.
What would settle it
A single graph of treewidth k whose inversion graph has diameter less than 2k, or a single degree-3 graph whose inversion graph has diameter greater than 3.
read the original abstract
In an oriented graph $\overrightarrow{G}$, the inversion of a subset $X$ of vertices is the operation that reverses the orientation of all arcs with both end-vertices in $X$. The inversion graph of a graph $G$, denoted by $\mathcal{I}(G)$, is the graph whose vertices are orientations of $G$ in which two orientations $\overrightarrow{G_1}$ and $\overrightarrow{G_2}$ are adjacent if and only if there is an inversion transforming $\overrightarrow{G_1}$ into $\overrightarrow{G_2}$.The inversion diameter of a graph $G$ is the diameter of its inversion graph $\mathcal{I}(G)$, denoted by $\mathrm{diam}(\mathcal{I}(G))$.Havet, H\"orsch, and Rambaud~(2024) first proved that for $G$ of treewidth $k$, $\mathrm{diam}(\mathcal{I}(G)) \le 2k$, and that there are graphs of treewidth $k$ with inversion diameter $k+2$.In this paper, we construct graphs of treewidth $k$ with inversion diameter $2k$, which implies that the previous upper bound $\mathrm{diam}(\mathcal{I}(G)) \le 2k$ is tight.Moreover, for graphs with maximum degree $\Delta$, Havet, H\"orsch, and Rambaud~(2024) proved $\mathrm{diam}(\mathcal{I}(G)) \le 2\Delta-1$ and conjectured that $\mathrm{diam}(\mathcal{I}(G)) \le \Delta$. We prove the conjecture when $\Delta=3$ with the help of computer calculations.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript constructs explicit families of graphs with treewidth exactly k whose inversion graphs I(G) have diameter 2k, establishing that the upper bound diam(I(G)) ≤ 2k proved by Havet et al. is tight. It additionally proves that diam(I(G)) ≤ 3 for every graph G with maximum degree 3, confirming the Δ-conjecture in the cubic case by means of computer-assisted enumeration and diameter computation.
Significance. If the constructions are correct and the computer verification is exhaustive and free of enumeration or algorithmic error, the results close the gap on treewidth bounds and resolve the open conjecture for Δ=3. The explicit constructions supply matching lower bounds that can be directly inspected, while the degree-3 result provides the first universal bound better than the general 2Δ−1 estimate.
major comments (2)
- [§4] §4 (computer-assisted proof of diam(I(G))≤3 for Δ=3): the claim rests on exhaustive enumeration and diameter computation whose method, completeness criterion, and implementation are not described in sufficient detail to permit independent verification; no source code, enumerated graph list, or error-analysis is supplied, rendering the central universal bound non-reproducible from the text alone.
- [§3] §3 (treewidth-k constructions): while the graphs are stated to have treewidth exactly k and inversion diameter 2k, the manuscript does not exhibit an explicit tree decomposition of width k or a self-contained argument that no smaller-width decomposition exists, which is required to confirm the lower-bound examples achieve the claimed treewidth parameter.
minor comments (2)
- [Abstract] The abstract and introduction cite Havet et al. (2024) without a corresponding bibliography entry; ensure the reference is complete and consistent.
- [§2] Notation for the inversion graph I(G) and the inversion operation is introduced clearly but the distinction between oriented graphs and their underlying undirected graphs could be reinforced with a small illustrative figure in §2.
Simulated Author's Rebuttal
We thank the referee for their thorough review and constructive comments. We address the two major concerns point by point below and will revise the manuscript accordingly to improve reproducibility and rigor.
read point-by-point responses
-
Referee: [§4] §4 (computer-assisted proof of diam(I(G))≤3 for Δ=3): the claim rests on exhaustive enumeration and diameter computation whose method, completeness criterion, and implementation are not described in sufficient detail to permit independent verification; no source code, enumerated graph list, or error-analysis is supplied, rendering the central universal bound non-reproducible from the text alone.
Authors: We agree that the description of the computer-assisted enumeration and verification is insufficient for independent reproduction. In the revised version, we will expand the relevant section to include a detailed description of the enumeration method (including the generation of all non-isomorphic graphs with maximum degree 3 up to the necessary order), the completeness criterion, the implementation (software and algorithms used for diameter computation), and an error analysis. We will also make the source code and the full list of enumerated graphs available via a public repository or supplementary material. revision: yes
-
Referee: [§3] §3 (treewidth-k constructions): while the graphs are stated to have treewidth exactly k and inversion diameter 2k, the manuscript does not exhibit an explicit tree decomposition of width k or a self-contained argument that no smaller-width decomposition exists, which is required to confirm the lower-bound examples achieve the claimed treewidth parameter.
Authors: We agree that an explicit verification of treewidth is required for the constructions to be fully self-contained. In the revision, we will add explicit tree decompositions of width k for the base cases and the inductive constructions, together with a self-contained argument establishing that the treewidth is at least k (via the presence of a K_{k+1} minor or an equivalent lower-bound technique). This will confirm that the examples achieve inversion diameter exactly 2k at treewidth k. revision: yes
Circularity Check
No circularity; claims rest on explicit constructions and computational verification
full rationale
The paper establishes the treewidth-k lower bound via explicit graph constructions (verifiable by direct inspection of treewidth and inversion distances) and proves the Δ=3 case via computer enumeration of relevant graphs. These steps do not reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The cited upper bounds and conjecture come from Havet et al. (2024), a distinct author group. No equations or arguments in the abstract or described claims exhibit the enumerated circularity patterns.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions of treewidth, oriented graphs, inversion of a vertex subset, and the inversion graph are assumed.
Forward citations
Cited by 1 Pith paper
-
Increasing arc-connectivity by bounded- and fixed-size inversions
Inversions of size exactly p characterize when large digraphs become k-arc-strong, while at most p-sized inversions admit a (4k-2+ε)-approximation for the minimum number needed and are NP-hard and APX-hard to optimize.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.