Pith. sign in

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.

arxiv 2607.07697 v1 pith:SYS5CALL submitted 2026-07-08 math.CO cs.DM

Induced ErdH{o}s--P\'osa property for long holes, long thetas, and beyond

classification math.CO cs.DM MSC 05C7005C8305C85
keywords induced Erdős–Pósainduced minorslong holesthetasdominated balanced separatorsQPTASMaximum Weight Independent Set
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves that long cycles and long thetas, viewed as induced minors, obey an induced Erdős–Pósa property: in any graph you can either pack many pairwise non-adjacent copies of them, or hit every copy with the closed neighborhoods of only O(tk log k) vertices. The argument works by building short t-models of a core graph and repeatedly adding carefully chosen ears until the model becomes rich enough to apply classical packing theorems for cycles or thetas; the remaining components are then handled by recursion. Because the same bound also produces small dominated balanced separators in graphs that exclude k such thetas, the authors obtain a quasipolynomial-time approximation scheme for Maximum Weight Independent Set (and several generalizations) on those graphs. A sympathetic reader cares because the result settles a concrete special case of two widely discussed conjectures that aim to lift classical minor theorems into the induced-minor world.

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).

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

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)
  1. [§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.
  2. [§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.
  3. [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.
  4. [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

0 steps flagged

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

0 free parameters · 4 axioms · 2 invented entities

The paper rests on standard graph-theoretic notions (induced minors, closed neighborhoods, treewidth, CMSO) plus two external packing theorems. No free parameters are fitted; the O(tk log k) bound inherits its logarithmic factor from the classical packing functions. The short t-model and ear-addition operations are definitional tools, not postulated physical entities.

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).
    Used as a black box to extract cycle packings from the final short t-model in the hole case (§3).
  • 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.
    Analogous black-box packing used for the 3PC/theta case (§5–6).
  • standard math A graph is a cactus iff it contains no theta as a subgraph (Proposition 5.3).
    Elementary characterization used to bound the size of theta-free subcubic graphs.
  • domain assumption Induced-minor models of planar graphs can be assumed to have singleton bags on degree-⩽2 vertices outside cycles (Lemma 4.3).
    Standard cleaning lemma for induced-minor models, invoked to relate Θ_t and Ξ_⩾t.
invented entities (2)
  • short t-model (guarded t-model with bounded bags and controlled ears) no independent evidence
    purpose: Captures an induced-minor model of a t-subdivision while allowing controlled growth by ears that preserve the shortness invariants needed for recursion.
    Definitional device introduced in §2; no independent existence claim outside the proofs.
  • t-long three-path-configuration (Ξ_⩾t) no independent evidence
    purpose: Algorithmically tractable proxy for Θ_t that still contains long cycles and thetas as induced minors.
    Technical intermediate object; detection is n^{O(t)} while Θ_t detection remains open.

pith-pipeline@v1.1.0-grok45 · 44539 in / 2885 out tokens · 35682 ms · 2026-07-10T18:13:10.241157+00:00 · methodology

0 comments
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}
}
Share X Bluesky LinkedIn Reddit HN
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

Figures reproduced from arXiv: 2607.07697 by Amadeus Reinald, Jadwiga Czy\.zewska, Marcin Pilipczuk, Pawe{\l} Rz\k{a}\.zewski, Tom\'a\v{s} Masa\v{r}\'ik.

Figure 1
Figure 1. Figure 1: Three minimal (with respect to the number of degree-2 vertices) [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Adding an ear to a short t-model, creating vertices x and y and an edge g ′ between them. Shown here are the two possible cases of ear addition: with endpoints on the same edge of H (left) and with endpoints on two distinct edges (right). The grey blobs depict vertex bags and the highlighted parts of paths depict vertices that are mandatorily in the guard set R. (iii) All other new edge bags contain paths … view at source ↗
Figure 3
Figure 3. Figure 3: An induced minor model of Θt that does not contain Ξ⩾t−1. Shaded areas indicate the sets of vertices corresponding to the degree-3 vertices of Θt , and other vertices are represented by single vertices. Now we are ready to prove Lemma 1.4. Proof of Lemma 1.4. To prove the first item, it is enough to consider induced minor models of Θt+2, as Θ⩾t+2 contains Θt+2 as an induced minor. Denote the degree-3 verti… view at source ↗
Figure 4
Figure 4. Figure 4: A Θ0 with an ear connecting distinct edges added. Suppose then that H is proper-maximal, and consider the connected components of G − N[R]. If no compo￾nent contains a Ξ⩾t , then X := R is a C-winning scenario of the first type for G and t. If at least two components contain a Ξ⩾t , X := R is a C-winning scenario of the second type. Thus, we may assume that exactly one com￾ponent, say D, of G − N[R] contai… view at source ↗
Figure 5
Figure 5. Figure 5: Above: H ′ (S) for P(S) ̸= ∅ has two edges whose deletion destroys all thetas — these are marked red. Below: the two most interesting cases how an ear can be added to H ′ (S). Hence, as D(S) ⊆ D and e is the unique edge of H such that D intersects N[η(e)], D(S) intersects exactly one of N[η(uoS)] or N[η(voS)]. Depending on which one is intersected, we say that S is of u-type or v-type, respectively. (Note … view at source ↗
Figure 6
Figure 6. Figure 6: The situation after Claim 2. The path P ′ contains two long subpaths Q′ 1 , Q′ 2 starting at vℓ , vr, while Q′ 3 starts at v ′ and avoids N[P ′ ] \ {v ′ , v}. Let q3 be the terminal vertex of Q′ 3 The big component of D3 := BIG(G−(N[P ′ ]∪ N[Q′ 3 ])) ̸= ∅ contains a vertex d3 having a neighbour x3 ∈ N(q3) \ (N[P ′ ] ∪ N[Q′ 3 − {q3}]). Intuitively, path d3x3q3 guarantees sort of an exclusive connection betw… view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Forbidding anticomplete planar minors: Induced Erd\H{o}s--P\'osa property and Maximum Independent Set in QP

    math.CO 2026-07 accept novelty 7.5

    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

41 extracted references · 41 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [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. [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. [3]

    An Induced

    Hickingbotham, Robert and Joret, Gwena. An Induced. 2025 , journal =. 2512.17232 , eprinttype =

  4. [4]

    Erd\H{o}s--P\'{o}sa property of cycles that are far apart

    Vida Dujmovi. CoRR , volume =. 2024 , xdoi =. 2412.13893 , eprinttype =

  5. [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. [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. [7]

    Fundamenta Mathematicae , volume =

    Karl Menger , title =. Fundamenta Mathematicae , volume =. doi:10.4064/FM-10-1-96-115 , year =

  8. [8]

    Acta Mathematica Academiae Scientiarum Hungaricae , volume =

    Tibor Gallai , title =. Acta Mathematica Academiae Scientiarum Hungaricae , volume =. 1964 , doi =

  9. [9]

    Seymour , title =

    Neil Robertson and Paul D. Seymour , title =. Journal of Combinatorial Theory, Series B , volume =. 1995 , doi =

  10. [10]

    On Independent Circuits Contained in a Graph , journal =

    Paul Erd. On Independent Circuits Contained in a Graph , journal =. 1965 , doi =

  11. [11]

    Seymour , title =

    Neil Robertson and Paul D. Seymour , title =. Journal of Combinatorial Theory, Series B , volume =. 1986 , doi =

  12. [12]

    Etienne Birmel. The. Combinatorica , volume =. 2007 , doi =

  13. [13]

    Journal of Graph Theory , volume =

    Carsten Thomassen , title =. Journal of Graph Theory , volume =. 1988 , doi =

  14. [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 =

  15. [15]

    Reed , title =

    Bruce A. Reed , title =. Combinatorica , volume =. 1999 , doi =

  16. [16]

    Packing Cycles Through Prescribed Vertices , journal =

    Naonori Kakimura and Ken. Packing Cycles Through Prescribed Vertices , journal =. 2011 , doi =

  17. [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 =

  18. [18]

    Peter Gartland , title =

  19. [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 =

  20. [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 =

  21. [21]

    Fomin and

    Marek Cygan and Fedor V. Fomin and. Parameterized Algorithms , series =. 2015 , doi =

  22. [22]

    Subexponential-time algorithms for

    G. Subexponential-time algorithms for. Algorithmica , volume =. 2019 , doi =

  23. [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. [24]

    Journal of Combinatorial Theory, Series B , volume =

    Cl. Journal of Combinatorial Theory, Series B , volume =. 2024 , doi =

  25. [25]

    Tree decompositions meet induced matchings:

    Paloma T. Tree decompositions meet induced matchings:. Journal of Computer and System Sciences , volume =. 2026 , doi =

  26. [26]

    Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number , journal =

    Daniel Lokshtanov and Micha. Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number , journal =. 2026 , eprint =

  27. [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 =

  28. [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 =

  29. [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 =

  30. [30]

    Dimitris Chatzidimitriou and Jean. An. Algorithmica , volume =. 2018 , xurl =. doi:10.1007/s00453-017-0313-5 , timestamp =

  31. [31]

    Discrete Applied Mathematics , volume =

    Carla Groenland and Karolina Okrasa and Alex Scott and Paul Seymour and Pawe. Discrete Applied Mathematics , volume =. 2019 , doi =

  32. [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. [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. [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 =

  35. [35]

    A coarse

    Jungho Ahn and Kwon, O-joung , howpublished =. A coarse. 2026 , note =

  36. [36]

    Detecting

    Cl. Detecting. Combinatorial Algorithms -- 35th International Workshop, IWOCA 2024 , series =. 2024 , publisher =

  37. [37]

    Induced Disjoint Paths Without an Induced Minor , booktitle =

    Pierre Aboulker and. Induced Disjoint Paths Without an Induced Minor , booktitle =. 2025 , publisher =

  38. [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 =

  39. [39]

    Journal of Computer and System Sciences , volume =

    Nicolas Bousquet and Cl. Journal of Computer and System Sciences , volume =. 2026 , doi =

  40. [40]

    Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star

    Cl. CoRR , volume =. 2024 , xdoi =. 2402.11222 , eprinttype =

  41. [41]

    Combinatorica , volume =

    Agelos Georgakopoulos and Panos Papasoglu , title =. Combinatorica , volume =. 2025 , xurl =. doi:10.1007/S00493-025-00150-6 , timestamp =