REVIEW 4 minor 1 cited by
Long induced cycles and thetas pack or are hit by O(tk log k) neighborhoods.
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · grok-4.5
2026-07-10 18:13 UTC pith:SYS5CALL
load-bearing objection Solid special cases of two open conjectures via a clean short-model + ear framework; the packing step after ear growth is controlled and the proofs check out.
Induced ErdH{o}s--P\'osa property for long holes, long thetas, and beyond
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every fixed t, both the cycle C_t and the theta Θ_t have the induced Erdős–Pósa property under the induced-minor relation: any graph either contains k pairwise vertex-disjoint anti-adjacent induced-minor models of the object, or admits a set X of size O(tk log k) whose closed neighborhood hits every such model.
What carries the argument
The short t-model of a multigraph H (together with controlled ear addition that preserves shortness). It encodes an induced-minor model whose bags are short enough that classical packing theorems for cycles or thetas inside H translate directly into an induced packing of long holes or long three-path configurations in the original graph.
Load-bearing premise
The classical packing theorems for cycles and for thetas still apply after the ear-addition process has introduced only a controlled number of parallel edges and low-degree vertices.
What would settle it
A concrete infinite family of graphs in which the maximum number of pairwise anti-adjacent induced C_t-minors (or Θ_t-minors) is k, yet every hitting set of closed neighborhoods has size ω(tk log k).
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that for every fixed t, both long cycles C_t and long thetas Θ_t have the induced Erdős–Pósa property with respect to the induced-minor relation: every graph G either contains k pairwise vertex-disjoint anti-adjacent induced-minor models of the object, or admits a set X of size O(tk log k) whose closed neighbourhood hits every such model. The algorithmic version is obtained for the intermediate object Ξ_⩾t (t-long three-path configurations) via short t-models, controlled ear addition, and packing theorems for cycles and thetas in nearly-cubic multigraphs; the existential statements for C_t and Θ_t follow by reduction. The same machinery yields O(tk log k)-dominated balanced separators in the corresponding free classes, confirming a special case of the Gartland–Lokshtanov conjecture and producing a QPTAS for MWIS (and hereditary (tw⩾r,ψ)-MWIS) in kΘ_t-induced-minor-free graphs.
Significance. The work settles a natural special case of the induced-minor Erdős–Pósa conjecture of Ahn–Gollin–Huynh–Kwon and of the dominated-separator conjecture of Gartland–Lokshtanov, both of which have been open even for cycles and thetas. The short-t-model / ear-decomposition technique is cleanly developed and reusable; the packing lemma for thetas (Theorem 5.2) that accounts for parallel edges and low-degree vertices is a useful technical contribution in its own right. The algorithmic consequences (QPTAS for MWIS and hereditary CMSO2 problems) are immediate from known blob-graph machinery once the separators are available, and the paper carefully isolates the remaining open detection problem for Θ_t itself. The O(tk log k) bound matches the classical non-induced order of magnitude up to the linear factor in t, and the lower-bound discussion is honest.
minor comments (4)
- [§3, proof of Theorem 1.3] The constant λ = 896(λ_Sim + 1) appearing in the proof of Theorem 1.3 (and the analogous constant in §6.3) is never written out explicitly in the statement of the theorems; a short remark that the O-notation hides a concrete (albeit large) absolute constant would help readers who wish to track the dependence.
- [§4.1, Figure 3] Figure 3 is referenced as showing an induced-minor model of Θ_t that does not contain Ξ_⩾t-1, but the caption and surrounding text could more clearly label the degree-3 bags versus the degree-2 vertices so that the necessity of the +2 slack in Lemma 1.4 is immediately visible.
- [Definition 2.5] In the definition of a short t-model (Definition 2.5) the phrase “any ear of distance at least t+3 is of length more than t” is slightly ambiguous when the ear is a loop on a single edge; a parenthetical clarification would remove any doubt.
- [Theorem 1.7] The algorithmic claim of Theorem 1.7 states running time n^{O(tk log k)}; it would be useful to note that the exponent is linear in the size of the separator returned by the recursive procedure, so that the dependence is fully explicit.
Circularity Check
No circularity: pure combinatorial packing/hitting proofs built from classical external theorems and self-contained ear-model constructions.
full rationale
The derivation chain for Theorems 1.3, 1.5 and 1.6 proceeds by constructing short t-models (Defs. 2.1/2.5, Lemmas 2.6/6.3–6.4), controlled ear addition that preserves shortness (Lemmas 2.8–2.9, Observation 2.11), maximality arguments that isolate components (Lemmas 2.12–2.13, 6.7), and packing of cycles/thetas in the resulting nearly-cubic multigraphs via Simonovits (Thm 1.14) and the new Thm 5.2 (itself derived from the external CRST packing theorem). The O(tk log k) bounds arise by explicit charging that absorbs the packing functions f_Sim and f_Θ together with the O(t) growth of the reserved set R; no parameter is fitted to data, no uniqueness theorem is imported from the authors’ prior work to force the form of the result, and no claimed prediction is definitionally identical to an input. The reduction from the induced Erdős–Pósa property to dominated balanced separators (Lemma 8.1 + Cor. 7.6) is likewise a direct, non-circular application. All external citations are classical or independent packing results used verbatim; the paper is self-contained against those benchmarks.
Axiom & Free-Parameter Ledger
axioms (4)
- standard math Simonovits’ theorem: every subcubic multigraph of minimum degree ⩾2 with ⩾f_Sim(k)=O(k log k) degree-3 vertices contains k vertex-disjoint cycles (Theorem 1.14).
- standard math Chatzidimitriou–Raymond–Sau–Thilikos packing theorem for thetas (Theorem 5.4) together with the cactus bound of Lemma 5.5, yielding the new packing Theorem 5.2 for nearly-cubic multigraphs.
- standard math A graph is a cactus iff it contains no theta as a subgraph (Proposition 5.3).
- domain assumption Induced-minor models of planar graphs can be assumed to have singleton bags on degree-⩽2 vertices outside cycles (Lemma 4.3).
invented entities (2)
-
short t-model (guarded t-model with bounded bags and controlled ears)
no independent evidence
-
t-long three-path-configuration (Ξ_⩾t)
no independent evidence
Cite this review
Pith. "Pith review of Induced Erd\H{o}s--P\'osa property for long holes, long thetas, and beyond." pith.science (2026). https://pith.science/paper/SYS5CALL
@misc{pith2026260707697,
author = {Pith},
title = {Pith review of: Induced Erd\Hos--P\'osa property for long holes, long thetas, and beyond},
year = {2026},
howpublished = {\url{https://pith.science/paper/SYS5CALL}},
note = {Machine review of arXiv:2607.07697}
}
read the original abstract
The induced Erd\H{o}s--P\'osa property in graphs relates the maximum number of pairwise anti-adjacent copies of an object with the minimum number of neighborhoods required to hit all copies. In this paper, the objects we consider are long cycles and long thetas, both as induced minors. Let $C_t$ denote the cycle with $t$ vertices and let $\Theta_t$ be the graph consisting of three internally disjoint and anti-adjacent paths, each with $t$ internal vertices, connecting the same pair of distinct vertices. We show that for every fixed $t$, both $C_t$ and $\Theta_t$ have the induced Erd\H{o}s--P\'osa property with respect to the induced minor relation. More precisely, for every integer $k$ and every graph $G$, one of the following two outcomes occurs: (i) $G$ contains $k$ pairwise vertex-disjoint and anti-adjacent copies of $C_t$ (resp., $\Theta_t$) as induced minors, or (ii) there is a set $X \subseteq V(G)$ of size $\mathcal{O}(tk \log k)$ such that the set $N[X]$, consisting of $X$ and its neighbors, hits all $C_t$ (resp., all $\Theta_t$) induced minors in $G$. This resolves in a strong form a special case of a conjecture of Ahn, Gollin, Huynh, and Kwon [SODA 2025]. From these results we derive that graphs that exclude $k$ disjoint copies of $\Theta_t$ as an induced minor admit balanced separators consisting of the neighborhood of $\mathcal{O}(tk \log k)$ vertices. This in turn resolves a special case of a conjecture of Gartland and Lokshtanov and, combined with known techniques, yields a QPTAS for Maximum Weight Independent Set and a number of its generalizations.
Figures
Forward citations
Cited by 1 Pith paper
-
Forbidding anticomplete planar minors: Induced Erd\H{o}s--P\'osa property and Maximum Independent Set in QP
Planar minors have the induced Erdős–Pósa property; sparse kH-free graphs have logarithmic H-hitting sets and thus admit quasi-polynomial MIS.
Reference graph
Works this paper leans on
-
[1]
A counterexample to the coarse Menger conjecture , journal =
Tung Nguyen and Alex Scott and Paul Seymour , keywords =. A counterexample to the coarse Menger conjecture , journal =. 2025 , issn =. doi:https://doi.org/10.1016/j.jctb.2025.01.004 , url =
-
[2]
Grid induced minor theorem for graphs of small degree , journal =
Tuukka Korhonen , keywords =. Grid induced minor theorem for graphs of small degree , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.jctb.2023.01.002 , xurl =
-
[3]
Hickingbotham, Robert and Joret, Gwena. An Induced. 2025 , journal =. 2512.17232 , eprinttype =
-
[4]
Erd\H{o}s--P\'{o}sa property of cycles that are far apart
Vida Dujmovi. CoRR , volume =. 2024 , xdoi =. 2412.13893 , eprinttype =
work page internal anchor Pith review Pith/arXiv arXiv 2024
-
[5]
Journal of the London Mathematical Society , volume =
Liu, Chun-Hung , title =. Journal of the London Mathematical Society , volume =. doi:10.1112/jlms.12633 , year =
-
[6]
Journal of Combinatorial Theory, Series B , volume =
A tight. Journal of Combinatorial Theory, Series B , volume =. 2017 , issn =. doi:10.1016/j.jctb.2017.01.004 , author =
-
[7]
Fundamenta Mathematicae , volume =
Karl Menger , title =. Fundamenta Mathematicae , volume =. doi:10.4064/FM-10-1-96-115 , year =
-
[8]
Acta Mathematica Academiae Scientiarum Hungaricae , volume =
Tibor Gallai , title =. Acta Mathematica Academiae Scientiarum Hungaricae , volume =. 1964 , doi =
work page 1964
-
[9]
Neil Robertson and Paul D. Seymour , title =. Journal of Combinatorial Theory, Series B , volume =. 1995 , doi =
work page 1995
-
[10]
On Independent Circuits Contained in a Graph , journal =
Paul Erd. On Independent Circuits Contained in a Graph , journal =. 1965 , doi =
work page 1965
-
[11]
Neil Robertson and Paul D. Seymour , title =. Journal of Combinatorial Theory, Series B , volume =. 1986 , doi =
work page 1986
-
[12]
Etienne Birmel. The. Combinatorica , volume =. 2007 , doi =
work page 2007
-
[13]
Journal of Graph Theory , volume =
Carsten Thomassen , title =. Journal of Graph Theory , volume =. 1988 , doi =
work page 1988
-
[14]
Journal of Combinatorial Theory, Series B , volume =
Eun Jung Kim and Kwon, O-joung , title =. Journal of Combinatorial Theory, Series B , volume =. 2020 , doi =
work page 2020
- [15]
-
[16]
Packing Cycles Through Prescribed Vertices , journal =
Naonori Kakimura and Ken. Packing Cycles Through Prescribed Vertices , journal =. 2011 , doi =
work page 2011
-
[17]
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
Jungho Ahn and Jochen Pascal Gollin and Tony Huynh and Kwon, O-joung , title =. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2025 , publisher =
work page 2025
-
[18]
Peter Gartland , title =
-
[19]
Finding Large Induced Sparse Subgraphs in
Peter Gartland and Daniel Lokshtanov and Marcin Pilipczuk and Micha. Finding Large Induced Sparse Subgraphs in. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021) , pages =. 2021 , publisher =
work page 2021
-
[20]
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) , series =
Giacomo Paesani and Dani. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) , series =. 2021 , publisher =
work page 2021
- [21]
-
[22]
Subexponential-time algorithms for
G. Subexponential-time algorithms for. Algorithmica , volume =. 2019 , doi =
work page 2019
-
[23]
Dominated Balanced Separators in Wheel-Induced-Minor-Free Graphs , journal =
Maria Chudnovsky and Jochen Pascal Gollin and Matja. Dominated Balanced Separators in Wheel-Induced-Minor-Free Graphs , journal =. 2025 , xdoi =. 2512.12329 , eprinttype =
-
[24]
Journal of Combinatorial Theory, Series B , volume =
Cl. Journal of Combinatorial Theory, Series B , volume =. 2024 , doi =
work page 2024
-
[25]
Tree decompositions meet induced matchings:
Paloma T. Tree decompositions meet induced matchings:. Journal of Computer and System Sciences , volume =. 2026 , doi =
work page 2026
-
[26]
Daniel Lokshtanov and Micha. Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number , journal =. 2026 , eprint =
work page 2026
-
[27]
A New Proof and Generalizations of a Theorem of
Mikl. A New Proof and Generalizations of a Theorem of. Acta Mathematica Academiae Scientiarum Hungaricae , volume =. 1967 , doi =
work page 1967
-
[28]
Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
Maria Chudnovsky and Peter Gartland and Sepehr Hajebi and Daniel Lokshtanov and Sophie Spirkl , title =. Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2025 , doi =
work page 2025
-
[29]
Journal of Combinatorial Theory, Series B , volume =
Maria Chudnovsky and Sepehr Hajebi and Daniel Lokshtanov and Sophie Spirkl , title =. Journal of Combinatorial Theory, Series B , volume =. 2026 , doi =
work page 2026
-
[30]
Dimitris Chatzidimitriou and Jean. An. Algorithmica , volume =. 2018 , xurl =. doi:10.1007/s00453-017-0313-5 , timestamp =
-
[31]
Discrete Applied Mathematics , volume =
Carla Groenland and Karolina Okrasa and Alex Scott and Paul Seymour and Pawe. Discrete Applied Mathematics , volume =. 2019 , doi =
work page 2019
-
[32]
Problems from the world surrounding perfect graphs , journal =
Gy. Problems from the world surrounding perfect graphs , journal =. doi:10.4064/am-19-3-4-413-441 , pages =
-
[33]
20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) , pages =
Bonnet,. 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) , pages =. 2026 , volume =. doi:10.4230/LIPIcs.SWAT.2026.9 , annote =
-
[34]
Quasi-Polynomial Time Approximation Schemes for the
Maria Chudnovsky and Marcin Pilipczuk and Micha. Quasi-Polynomial Time Approximation Schemes for the. SIAM Journal on Computing , volume =. 2024 , doi =
work page 2024
- [35]
- [36]
-
[37]
Induced Disjoint Paths Without an Induced Minor , booktitle =
Pierre Aboulker and. Induced Disjoint Paths Without an Induced Minor , booktitle =. 2025 , publisher =
work page 2025
-
[38]
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =
Tuukka Korhonen and Daniel Lokshtanov , title =. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2024 , publisher =
work page 2024
-
[39]
Journal of Computer and System Sciences , volume =
Nicolas Bousquet and Cl. Journal of Computer and System Sciences , volume =. 2026 , doi =
work page 2026
-
[40]
Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
Cl. CoRR , volume =. 2024 , xdoi =. 2402.11222 , eprinttype =
work page internal anchor Pith review Pith/arXiv arXiv 2024
-
[41]
Agelos Georgakopoulos and Panos Papasoglu , title =. Combinatorica , volume =. 2025 , xurl =. doi:10.1007/S00493-025-00150-6 , timestamp =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.