Pith. sign in

REVIEW 5 minor 1 cited by

Graphs without k non-adjacent planar minors can be made free of that minor by deleting f(k) neighborhoods, and admit quasi-polynomial Maximum Independent Set.

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 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 01:28 UTC pith:L2OLHWKK

load-bearing objection Solid induced EPP for planar minors plus QP MIS; the linear-protrusion engine is the real novelty and the proofs check out.

arxiv 2607.09646 v1 pith:L2OLHWKK submitted 2026-07-10 math.CO cs.DM

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

Maria Chudnovsky , Amadeus Reinald , St\'ephan Thomass\'e This is my paper
classification math.CO cs.DM MSC 05C8305C8505C69
keywords induced Erdős–Pósaplanar minorsprotrusionsMaximum Independent Setquasi-polynomial algorithmtree-widthkH-free graphscoarse graph theory
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.

Classical Erdős–Pósa duality says that if a graph has no k vertex-disjoint cycles (or, more generally, no k disjoint models of a fixed planar graph H), then a bounded-size set of vertices hits every such model. This paper lifts the duality one step into the induced setting: if there are no k pairwise non-adjacent H-minor models, then a bounded number of closed neighborhoods already hits every H-minor model. The same structural engine shows that the sparse members of the class have only logarithmic-size hitting sets and therefore logarithmic tree-width. Consequently Maximum Independent Set can be solved in quasi-polynomial time on every kH-free graph. The argument never needs the fine geometry of H; it works by proving that high-girth sparse kH-free graphs contain linearly many large independent protrusions that can be reduced while preserving both freeness and hitting-set size.

Core claim

For every planar graph H there is a function f such that every graph containing no k pairwise non-adjacent H-minor models admits a set X of size at most f(k) whose closed neighborhood hits every H-minor model. In the sparse case the same technique yields an H-hitting set of size O(log n), which immediately supplies a quasi-polynomial algorithm for Maximum Independent Set.

What carries the argument

The linear protrusion property (Theorem 13): every sparse kH-free graph of sufficiently large H-girth contains a linear number of pairwise independent p-protrusions of any prescribed size L. These protrusions can be replaced by smaller equivalent ones while preserving both kH-freeness and the size of a minimum H-hitting (or H-dominating) set, enabling an inductive reduction that produces the claimed bounds.

Load-bearing premise

After a bounded deletion that kills all small H-models, the remaining sparse kH-free graph of large H-girth still contains linearly many large independent protrusions; if that linear density fails, the whole reduction collapses.

What would settle it

Exhibit a single planar H, an integer k and an infinite family of kH-free graphs of large H-girth and no Kr,r subgraph in which the number of independent p-protrusions of size L is o(n) for every fixed L and p; any such family would refute the linear protrusion property and therefore both main theorems.

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

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Planar minors satisfy the induced Erdős–Pósa property (distance-2 packing versus radius-1 hitting).
  • Sparse kH-free graphs have logarithmic tree-width and therefore admit polynomial-time dynamic programming for many problems once the O(log n) hitting set is guessed.
  • Maximum Independent Set is solvable in n^{O(log n)} time on every kH-free graph.
  • The same protrusion-reduction engine yields an induced Erdős–Pósa theorem for every planar H, confirming the d=2 case of the coarse planar-minor conjecture.

Where Pith is reading between the lines

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

  • The same linear-protrusion argument may extend to other hereditary packing conditions that force linear neighborhood complexity, potentially giving quasi-polynomial MIS for broader classes.
  • If the induced Menger conjecture for distance-2 paths is true, the same technique could produce an induced grid-minor theorem and settle polynomial-time MIS for planar induced-minor-free graphs.
  • Recognition of kH-free graphs remains open for most H; a constructive version of the protrusion reduction would immediately give a quasi-polynomial recognition algorithm.

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

Summary. The paper proves that planar minors satisfy the induced Erdős–Pósa property: for every planar H there is a function f such that every kH-free graph G (no k pairwise non-adjacent H-minor models) admits a set X of size at most f(k) whose closed neighbourhoods hit all H-minor models (Theorem 1). The same linear-protrusion machinery yields that sparse kH-free graphs have an H-hitting set of size O(log n) (Theorem 3) and therefore logarithmic tree-width, which, after a quasi-polynomial branching reduction to the sparse case, produces an n^{O(log n)}-time algorithm for Maximum Independent Set on kH-free graphs (Theorem 2). The technical core is a linear protrusion property for high-girth kH-free graphs (Theorem 13), obtained by lifting a trichotomy for tree-width-t graphs (Theorem 12) via bounded-expansion facts, together with folio-preserving protrusion reductions that keep both kH-freeness and the numerical values of τ_H and γ_H (Lemmas 8–11, 15).

Significance. The result settles the d=2 case of the coarse planar-minor Erdős–Pósa conjecture of Albrechtsen–Davies in a strong form (radius-1 balls) and simultaneously generalises the quasi-polynomial MIS algorithm previously known only for kK_3-free graphs. The linear-protrusion property itself is a reusable structural tool. The argument is self-contained once the classical grid-minor theorem and the bounded-expansion results of Dvořák and Gajarský et al. are granted; all parameters are finite existential bounds and the reductions are one-directional, so the induction is clean. The paper therefore supplies both a new packing-hitting duality and a concrete algorithmic consequence of genuine interest to structural and algorithmic graph theory.

minor comments (5)
  1. In the overview (Section 1.1) and again before Theorem 14 the authors assume H connected “for the sake of exposition”; the disconnected case is handled later by Lemma 15 and an induction on the number of components. A single sentence at the beginning of Section 5 stating that the connected case is proved first would make the logical order clearer.
  2. The constant p is defined as m+2t in the preliminaries and later as 2t+m; both are identical, but a uniform notation would avoid a momentary double-take.
  3. In the proof of Theorem 12 the constant c_L = 1/40 c_t (t+1) L^3 appears without an explicit derivation of the numerical factors; while the existence of some positive c_L is all that is needed, a short parenthetical remark that the factors arise from the three-case analysis would help a reader who wants to track the constants.
  4. A few typographical slips remain: “Tothisday” (p. 1), “variantsofcycleshaveconstituted” (p. 1), and the arXiv identifier of the companion paper on induced long holes is given as 2607.07697 (which may be a placeholder).
  5. The recognition question for kH-free graphs is mentioned only for H=K_3; a brief pointer to the status for general planar H would round out the open-problems paragraph.

Circularity Check

0 steps flagged

No significant circularity: self-contained inductive proofs via linear protrusions and folio-preserving reductions, relying only on classical external theorems.

full rationale

The derivation chain for Theorems 1 and 3 proceeds by induction on k (and number of components of H), reducing high-girth sparse kH-free graphs via the linear protrusion property (Theorem 13, proved from the tree-width trichotomy of Theorem 12 plus bounded-expansion/linear-neighborhood-complexity facts of Theorem 6 from Dvořák and Gajarský et al.) and then replacing large p-protrusions by smaller ones that preserve kH-freeness and the numerical values of τ_H or γ_H (Lemmas 8–11 and 15, via finiteness of (s,f)-folios). All parameters (p = m + 2t, L large enough for folio types, g_L, c_L, etc.) are finite existential bounds chosen once and for all; none is fitted to the target f(k) or defined in terms of the conclusion. The only external inputs are the Robertson–Seymour grid-minor theorem (for bounded tree-width of H-minor-free graphs) and the cited sparse-class facts; both are independent of the induced packing numbers. No self-definitional loops, no fitted-then-predicted quantities, no load-bearing self-citations of uniqueness theorems, and no renaming of known results. The QP algorithm of Theorem 2 is a direct consequence of the logarithmic hitting set plus standard DP on bounded-tree-width graphs. The proofs are therefore non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The paper rests on three classical external theorems (grid-minor, bounded expansion of sparse classes, Korhonen’s induced-grid theorem for bounded-degree graphs) plus the standard definition of protrusions and folios. All other constants (p = m+2t, L large enough for folio pigeonhole, gL, cL) are existentially quantified from those theorems; no free numerical parameters are fitted to data and no new physical or combinatorial entities are postulated.

axioms (4)
  • standard math Robertson–Seymour grid-minor theorem: H-minor-free graphs have bounded tree-width when H is planar (Theorem 5).
    Used to bound tree-width after an H-hitting set is deleted and to set the constant t.
  • standard math Sparse kH-free classes have bounded expansion, hence are degenerate and have linear neighborhood complexity (Theorem 6, citing Dvořák and Gajarský et al.).
    Supplies the constants c and δ that drive the linear-protrusion counting arguments.
  • standard math Bounded-degree kH-free graphs have bounded H-hitting set (Theorem 7, via Korhonen’s induced-grid theorem).
    Used to clean the low-degree part Y of a high-girth graph before applying the tree-width SLPP.
  • domain assumption There are only finitely many distinct (s,f)-folios and neighborhood folios of p-boundaried graphs of size less than any fixed L.
    Guarantees that every sufficiently large protrusion can be replaced by a strictly smaller equivalent one (definition of L in §§3 and 5).

pith-pipeline@v1.1.0-grok45 · 27726 in / 2624 out tokens · 26881 ms · 2026-07-13T01:28:23.323389+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Forbidding anticomplete planar minors: Induced Erd\H{o}s--P\'osa property and Maximum Independent Set in QP." pith.science (2026). https://pith.science/paper/L2OLHWKK

@misc{pith2026260709646,
  author       = {Pith},
  title        = {Pith review of: Forbidding anticomplete planar minors: Induced Erd\Hos--P\'osa property and Maximum Independent Set in QP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L2OLHWKK}},
  note         = {Machine review of arXiv:2607.09646}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The Erd\H{o}s--P\'osa theorem asserts that every graph $G$ with no $k$ disjoint cycles contains a set $X$ of $f(k)$ vertices such that $G\setminus X$ has no cycle. Robertson and Seymour showed that this Erd\H{o}s--P\'osa property also holds for $H$-minor models of any planar graph $H$. Equivalently, if $G$ has no $k$ minor models of $H$ pairwise at distance at least 1 (i.e. disjoint), then one can remove $f(k,H)$ balls of radius 0 (i.e. vertices) to make the graph $H$-minor free. We show that this coarse graph theory point of view generalizes to distance at least 2 versus radius 1 balls, yielding the induced Erd\H{o}s--P\'osa property for planar minors. Namely, every graph $G$ which does not contain $k$ pairwise non-adjacent minor models of a planar graph $H$ (we say that $G$ is $kH$-free) can be made $H$-minor free by removing $f(k,H)$ neighborhoods. The proof relies on the fact that sparse $kH$-free graphs have linearly many independent large protrusions. The same method gives that sparse $kH$-free graphs can be made $H$-minor free by deleting $O(\log n)$ vertices (and thus have logarithmic tree-width). This gives a quasi-polynomial algorithm for the Maximum Independent Set problem for $kH$-free graphs.

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. Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

    cs.DM 2026-07 conditional novelty 8.0

    For graphs of treewidth w and pathwidth w, neighbourhood complexity is exactly (k-w+1)2^w + w and (k-w+2)2^(w-1)+2k-w-2, with matching constructions; forests give floor(7k/3).

Reference graph

Works this paper leans on

43 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Abrishami, M

    T. Abrishami, M. Chudnovsky, S. Hajebi, and S. Spirkl. Induced subgraphs and tree decom- positions iii. three-path-configurations and logarithmic treewidth.Advances in Combinatorics, page 1–29, 2022

    2022

  2. [2]

    Abrishami, J

    T. Abrishami, J. Czyżewska, K. Kluk, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. On coarse tree decompositions and coarse balanced separators, 2025

    2025

  3. [3]

    J. Ahn, J. P. Gollin, T. Huynh, and O.-J. Kwon. A coarse erdős-pósa theorem. In Y. Azar and D. Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 3363–3381. SIAM, 2025

    2025

  4. [4]

    Albrechtsen, T

    S. Albrechtsen, T. Huynh, R. W. Jacobs, P. Knappe, and P. Wollan. A menger-type theorem for two induced paths.SIAM Journal on Discrete Mathematics, 38(2):1438–1450, May 2024

    2024

  5. [5]

    S. A. Amiri, K.-I. Kawarabayashi, S. Kreutzer, and P. Wollan. The erdos-posa property for directed graphs, 2016

    2016

  6. [6]

    Baste, I

    J. Baste, I. Sau, and D. M. Thilikos. Hitting minors on bounded treewidth graphs. i. general upper bounds.SIAM J. Discret. Math., 34(3):1623–1648, Jan. 2020. 17

    2020

  7. [7]

    H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos. (meta) kernelization.Journal of the ACM (JACM), 63(5):1–69, 2016

    2016

  8. [8]

    Bonamy, É

    M. Bonamy, É. Bonnet, N. Bousquet, P. Charbit, P. Giannopoulos, E. J. Kim, P. Rzazewski, F. Sikora, and S. Thomassé. EPTAS and subexponential algorithm for maximum clique on disk and unit ball graphs.J. ACM, 68(2):9:1–9:38, 2021

    2021

  9. [9]

    Bonamy, E

    M. Bonamy, E. Bonnet, N. Bousquet, P. Charbit, and S. Thomassé. EPTAS for max clique on disks and unit balls. In M. Thorup, editor,59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 568–579. IEEE Computer Society, 2018

    2018

  10. [10]

    Bonamy, E

    M. Bonamy, E. Bonnet, H. Déprés, L. Esperet, C. Geniet, C. Hilaire, S. Thomassé, and A. Wesolek. Sparse graphs with bounded induced cycle packing number have logarithmic treewidth. In N. Bansal and V. Nagarajan, editors,Proceedings of the 2023 ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 3006–

    2023

  11. [11]

    Chudnovsky and R

    M. Chudnovsky and R. Hickingbotham. Coarse balanced separators and tree-decompositions, 2025

    2025

  12. [12]

    Chudnovsky, M

    M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé. Quasi-polynomial time ap- proximation schemes for the maximum weight independent set problem in h-free graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2260–2278. SIAM, 2020

    2020

  13. [13]

    Czyżewska, T

    J. Czyżewska, T. Masařík, M. Pilipczuk, A. Reinald, and P. Rzążewski. Induced Erdős–Pósa property for long holes, long thetas, and beyond. arXiv:2607.07697, 2026. Preprint

    Pith/arXiv arXiv 2026

  14. [14]

    Davies and S

    J. Davies and S. Albrechtsen. Personal communication, 2026

    2026

  15. [15]

    Distel, U

    M. Distel, U. Giocanti, J. Hodor, C. Legrand-Duchesne, and P. Micek. A coarse gallai theorem. arXiv preprint arXiv:2601.18439, 2026

    arXiv 2026

  16. [16]

    Dujmović, G

    V. Dujmović, G. Joret, P. Micek, and P. Morin. Erdős–Pósa property of cycles that are far apart.CoRR, abs/2412.13893, 2024

    Pith/arXiv arXiv 2024

  17. [17]

    Z. Dvořák. Induced subdivisions and bounded expansion.European Journal of Combinatorics, 69:143–148, 2018

    2018

  18. [18]

    Erdős and L

    P. Erdős and L. Pósa. On independent circuits contained in a graph.Canadian Journal of Mathematics, 17:347–352, 1965

    1965

  19. [19]

    M. R. Fellows and M. A. Langston. An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations (extended abstract). In30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 520–525. IEEE Computer Society, 1989

    1989

  20. [20]

    F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470–479. IEEE Computer Society, 2012. 18

    2012

  21. [21]

    Gajarský, P

    J. Gajarský, P. Hliněný, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sánchez Villaamil, and S. Sikdar. Kernelization using structural parameters on sparse graph classes. Journal of Computer and System Sciences, 84:219–242, 2017

    2017

  22. [22]

    Gartland.Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes

    P. Gartland.Quasi-Polynomial Time Techniques for Independent Set and Beyond in Hereditary Graph Classes. PhD thesis, University of California, Santa Barbara, USA, 2023

    2023

  23. [23]

    Georgakopoulos and P

    A. Georgakopoulos and P. Papasoglu. Graph minors and metric spaces.Comb., 45(3):33, 2025

    2025

  24. [24]

    Gorsky, K

    M. Gorsky, K. Hendrey, and T. Huynh. The Erdős-Pósa property for prime-length cycles fails (and beyond).arXiv preprint arXiv:2605.04938, 2026

    Pith/arXiv arXiv 2026

  25. [25]

    Grzesik, T

    A. Grzesik, T. Klimošová, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithms for maximum weight independent set on p6-free graphs.ACM Trans. Algorithms, 18(1), Jan. 2022

    2022

  26. [26]

    Hickingbotham and G

    R. Hickingbotham and G. Joret. An inducedA-path theorem.CoRR, abs/2512.17232, 2025

    arXiv 2025

  27. [27]

    Kakimura, K.-i

    N. Kakimura, K.-i. Kawarabayashi, and D. Marx. Packing cycles through prescribed vertices. Journal of Combinatorial Theory, Series B, 101(5):378–381, 2011

    2011

  28. [28]

    E. J. Kim and O.-J. Kwon. Erdős–Pósa property of chordless cycles and its applications. Journal of Combinatorial Theory, Series B, 145:65–112, 2020

    2020

  29. [29]

    E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith, I. Sau, and S. Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions.ACM Trans. Algorithms, 12(2), Dec. 2015

    2015

  30. [30]

    Korhonen

    T. Korhonen. Grid induced minor theorem for graphs of small degree.Journal of Combinatorial Theory, Series B, 160:206–214, 2023

    2023

  31. [31]

    C.-H. Liu. Packing topological minors half-integrally.Journal of the London Mathematical Society, 106(3):2193–2267, 2022

    2022

  32. [32]

    Mousset, A

    F. Mousset, A. Noever, N. Škorić, and F. Weissenberger. A tight Erdős–Pósa function for long cycles.Journal of Combinatorial Theory, Series B, 125:21–32, 2017

    2017

  33. [33]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced paths in graphs without anticomplete cycles. Journal of Combinatorial Theory, Series B, 164:321–339, 2024

    2024

  34. [34]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Asymptotic structure IV. A counterexample to the weak coarse Menger conjecture, 2025

    2025

  35. [35]

    Nguyen, A

    T. Nguyen, A. D. Scott, and P. D. Seymour. A counterexample to the coarse menger conjecture. J. Comb. Theory B, 173:68–82, 2025

    2025

  36. [36]

    Pilipczuk, M

    M. Pilipczuk, M. Pilipczuk, and P. Rzążewski.Quasi-polynomial-time algorithm for Indepen- dent Set in <italic>P<sub>t</sub></italic>-free graphs via shrinking the space of induced paths, pages 204–209

  37. [37]

    Pontecorvi and P

    M. Pontecorvi and P. Wollan. Disjoint cycles intersecting a set of vertices.Journal of Combi- natorial Theory, Series B, 102(5):1134–1141, 2012

    2012

  38. [38]

    B. A. Reed. Mangoes and blueberries.Comb., 19(2):267–296, 1999. 19

    1999

  39. [39]

    B. A. Reed, N. Robertson, P. D. Seymour, and R. Thomas. Packing directed circuits.Comb., 16(4):535–554, 1996

    1996

  40. [40]

    Robertson and P

    N. Robertson and P. Seymour. Graph minors V. Excluding a planar graph.Journal of Com- binatorial Theory, Series B, 41(1):92–114, 1986

    1986

  41. [41]

    Robertson and P

    N. Robertson and P. Seymour. Graph minors XIII. The disjoint paths problem.Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995

    1995

  42. [42]

    Thomassen

    C. Thomassen. On the presence of disjoint subgraphs of a specified type.Journal of Graph Theory, 12(1):101–111, 1988

    1988

  43. [43]

    Czyżewska, T

    Édouard Bonnet, J. Czyżewska, T. Masařík, M. Pilipczuk, and P. Rzążewski. Qptas for mwis and finding large sparse induced subgraphs in graphs with few independent long holes, 2026. 20

    2026