pith. sign in

arxiv: 2412.14836 · v4 · pith:IJQOAP6Xnew · submitted 2024-12-19 · 💻 cs.DS · math.CO

Sparse induced subgraphs in P₇-free graphs of bounded clique number

Maria Chudnovsky , Jadwiga Czy\.zewska , Kacper Kluk , Marcin Pilipczuk , Pawe{\l} Rz\k{a}\.zewski This is my paper

Pith reviewed 2026-05-23 07:24 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords P7-free graphsbounded clique numberCMSO2 logicsparse induced subgraphspolynomial-time algorithmsinduced path exclusiondynamic programming
0
0 comments X

The pith

Problems of finding the largest sparse induced subgraph satisfying a CMSO2 property admit polynomial-time algorithms on P7-free graphs of bounded clique number.

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

The paper establishes that every fixed CMSO2-expressible property for maximum sparse induced subgraphs can be solved in polynomial time on P7-free graphs whose largest clique has constant size. This extends the recent polynomial-time result for the smaller class of P6-free graphs and moves closer to the belief that excluding any fixed induced path suffices for tractability. A sympathetic reader cares because the formalism captures many concrete problems including maximum-weight independent set, feedback vertex set, and vertex planarization.

Core claim

In P7-free graphs with bounded clique number, the problem of finding a maximum-weight induced subgraph whose property is expressible in counting monadic second-order logic with two free set variables admits a polynomial-time algorithm via dynamic programming over suitable decompositions.

What carries the argument

Dynamic programming over decompositions of P7-free graphs with bounded clique number, extending the approach previously used for P6-free graphs.

If this is right

  • Maximum-weight independent set is solvable in polynomial time on these graphs.
  • Feedback vertex set is solvable in polynomial time on these graphs.
  • Vertex planarization is solvable in polynomial time on these graphs.
  • Any other fixed CMSO2 property for sparse induced subgraphs is solvable in polynomial time on these graphs.

Where Pith is reading between the lines

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

  • The result suggests that further path exclusions may remain tractable once clique number is controlled.
  • It raises the question whether the clique-number bound can eventually be removed while keeping polynomial time.
  • The same decomposition ideas might apply to other hereditary classes that are close to path-free graphs.

Load-bearing premise

The structural properties of P7-free graphs with bounded clique number are close enough to those of P6-free graphs that the same dynamic-programming techniques apply.

What would settle it

A P7-free graph with clique number three on which maximum-weight independent set (a CMSO2 property) requires superpolynomial time.

read the original abstract

Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph, that satisfies some property definable in CMSO$_2$ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rz\k{a}\.zewski [STOC 2021], and a recent polynomial-time algorithm for $P_6$-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rz\k{a}\.zewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to $P_7$-free graphs of bounded clique number.

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

Summary. The manuscript claims a polynomial-time algorithm for the maximum sparse induced subgraph problem (including Max Weight Independent Set, Feedback Vertex Set, and Vertex Planarization) when the target property is CMSO₂-expressible, restricted to the class of P₇-free graphs with bounded clique number. The result extends the SODA 2024 polynomial-time algorithm for P₆-free graphs (Chudnovsky et al.) by establishing suitable structural decompositions that support dynamic programming.

Significance. If the central claim holds, the work provides the first polynomial-time result for these problems on P₇-free graphs (with the bounded-clique-number restriction) and supplies concrete evidence that the quasipolynomial algorithm of Gartland et al. (STOC 2021) can be improved to polynomial time for one additional path length. No machine-checked proofs or parameter-free derivations are claimed, but the result is algorithmically falsifiable on finite instances.

minor comments (4)
  1. [§1] §1, paragraph 3: the statement that the result 'extends polynomial-time tractability' should cite the precise theorem number from the SODA 2024 paper being extended.
  2. [§4.2] §4.2, Definition 4.3: the notation for the 'sparse' condition in the CMSO₂ formula is introduced without an explicit reference to the earlier definition in §2; this creates a minor forward-reference issue.
  3. [Figure 2] Figure 2: the decomposition tree diagram uses an unlabeled edge style that is not explained in the caption or in the surrounding text.
  4. [Theorem 5.1] Theorem 5.1: the running-time bound is stated as O(n^c) for some constant c; an explicit dependence on the clique-number bound ω would be helpful for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment, accurate summary of our contribution, and recommendation of minor revision. The report correctly identifies the extension of the SODA 2024 result for P6-free graphs to the P7-free case under the bounded-clique-number restriction, using structural decompositions for dynamic programming on CMSO2-expressible sparse induced subgraph problems.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper extends the P6-free polynomial-time CMSO2 result (cited from independent prior work by overlapping authors) to P7-free graphs of bounded clique number via structural decompositions and dynamic programming. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-definition, or load-bearing self-citation chain; the central extension is presented as building on externally established graph-theoretic facts without internal reduction to inputs. This is the expected non-finding for a proof-based algorithmic paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no free parameters, invented entities, or ad-hoc axioms beyond standard results in structural graph theory and logic; the contribution is an algorithmic extension.

axioms (1)
  • standard math Standard results from structural graph theory on induced-path-free graphs and CMSO2 logic
    The algorithm relies on known decompositions or properties of Pk-free graphs established in prior literature.

pith-pipeline@v0.9.0 · 5745 in / 1136 out tokens · 47393 ms · 2026-05-23T07:24:09.463401+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

39 extracted references · 39 canonical work pages · 1 internal anchor

  1. [1]

    Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawe ł Rzążewski, and Paul D. Seymour. Induced subgraphs of bounded treewidth and the container method. SIAM J. Comput., 53(3):624– 647, 2024

    work page 2024

  2. [2]

    Close relatives of feedback vertex set without single-exponential algorithms pa rameterized by treewidth

    Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell, and O -joung Kwon. Close relatives of feedback vertex set without single-exponential algorithms pa rameterized by treewidth. In Yixin Cao and Marcin Pilipczuk, editors, 15th International Symposium on Parameterized and Exact Com- putation, IPEC 2020, December 14-18, 2020, Hong Kong, China ( Virtual Conf...

    work page 2020

  3. [3]

    A logic- based algorithmic meta-theorem for mim-width

    Benjamin Bergougnoux, Jan Dreier, and Lars Jaffke. A logic- based algorithmic meta-theorem for mim-width. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM- SIAM Symposium on Discrete Algorithms, SODA 2023, Florence , Italy, January 22-25, 2023 , pages 3282–3304. SIAM, 2023

    work page 2023

  4. [4]

    Degeneracy of Pt-free and C>t-free graphs with no large complete bipartite subgraphs

    Marthe Bonamy, Nicolas Bousquet, Michał Pilipczuk, Paweł Rzążewski, Stéphan Thomassé, and Bartosz Walczak. Degeneracy of Pt-free and C>t-free graphs with no large complete bipartite subgraphs. J. Comb. Theory B , 152:353–378, 2022. 40

    work page 2022

  5. [5]

    Three-coloring and list three-coloring of graphs witho ut induced paths on seven ver- tices

    Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Oliver Schau dt, Maya Stein, and Mingxian Zhong. Three-coloring and list three-coloring of graphs witho ut induced paths on seven ver- tices. Comb., 38(4):779–801, 2018

    work page 2018

  6. [6]

    Better 3-coloring algorithms : Excluding a triangle and a seven vertex path

    Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeu r, Peter Maceli, Oliver Schaudt, Maya Stein, and Mingxian Zhong. Better 3-coloring algorithms : Excluding a triangle and a seven vertex path. Theor. Comput. Sci., 850:98–115, 2021

    work page 2021

  7. [7]

    Listing all potential ma ximal cliques of a graph

    Vincent Bouchitté and Ioan Todinca. Listing all potential ma ximal cliques of a graph. Theor. Comput. Sci., 276(1-2):17–32, 2002

    work page 2002

  8. [8]

    Treewidth and minimum fi ll-in: Grouping the minimal separators

    Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fi ll-in: Grouping the minimal separators. SIAM J. Comput. , 31(1):212–232, jan 2002

    work page 2002

  9. [9]

    Maximum Weight Independe nt Sets for (P7, triangle)- free graphs in polynomial time

    Andreas Brandstädt and Raffaele Mosca. Maximum Weight Independe nt Sets for (P7, triangle)- free graphs in polynomial time. Discret. Appl. Math., 236:57–65, 2018

    work page 2018

  10. [10]

    Bounding the mim-width of hereditary graph classes

    Nick Brettell, Jake Horsfield, Andrea Munaro, Giacomo Paesan i, and Daniël Paulusma. Bounding the mim-width of hereditary graph classes. J. Graph Theory , 99(1):117–151, 2022

    work page 2022

  11. [11]

    List k-colouring Pt -free graphs: A mim-width perspective

    Nick Brettell, Jake Horsfield, Andrea Munaro, and Daniël Paulu sma. List k-colouring Pt -free graphs: A mim-width perspective. Inf. Process. Lett., 173:106168, 2022

    work page 2022

  12. [12]

    Finding largeH-colorable subgraphs in hereditary graph classes

    Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rz ążewski, and Sophie Spirkl. Finding largeH-colorable subgraphs in hereditary graph classes. SIAM J. Discret. Math., 35(4):2357–2386, 2021

    work page 2021

  13. [13]

    Sparse induced subgraphs inP6-free graphs

    Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Micha ł Pilipczuk, and Paweł Rzążewski. Sparse induced subgraphs inP6-free graphs. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexa ndria, V A, USA, January 7-10, 2024, pages 5291–5299. SIAM, 2024

    work page 2024

  14. [14]

    Corneil, Yehoshua Perl, and Lorna K

    Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. A line ar recognition algorithm for cographs. SIAM J. Comput., 14(4):926–934, 1985

    work page 1985

  15. [15]

    Makowsky, and Udi Rotics

    Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization prob- lems on graphs of bounded clique width. In Juraj Hromkovic and Ondre j Sýkora, editors, Graph- Theoretic Concepts in Computer Science, 24th International W orkshop, WG ’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings , volume 1517 of Lecture N...

    work page 1998

  16. [16]

    Treewidth versus clique number

    Clément Dallard, Martin Milanič, and Kenny Storgel. Treewidth versus clique number. II. tree- independence number. J. Comb. Theory B , 164:404–442, 2024

    work page 2024

  17. [17]

    Bounding the v ertex cover number of a hyper- graph

    Guo Li Ding, Paul Seymour, and Peter Winkler. Bounding the v ertex cover number of a hyper- graph. Combinatorica, 14(1):23–34, March 1994

    work page 1994

  18. [18]

    Paths, trees, and flowers

    Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics , 17:449–467, 1965

    work page 1965

  19. [19]

    Fomin, Ioan Todinca, and Yngve Villanger

    Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induce d subgraphs via triangulations and CMSO. SIAM J. Comput., 44(1):54–87, 2015

    work page 2015

  20. [20]

    Independent set on Pk-free graphs in quasi-polynomial time

    Peter Gartland and Daniel Lokshtanov. Independent set on Pk-free graphs in quasi-polynomial time. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Scienc e, FOCS 2020, Durham, NC, USA, November 16-19, 2020 , pages 613–624. IEEE, 2020. 41

    work page 2020

  21. [21]

    Maximum weight independent set in graphs wit h no long claws in quasi- polynomial time

    Peter Gartland, Daniel Lokshtanov, Tomás Masařík, Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Maximum weight independent set in graphs wit h no long claws in quasi- polynomial time. In Bojan Mohar, Igor Shinkar, and Ryan O’Donne ll, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Va ncouver, BC, Canada...

    work page 2024

  22. [22]

    Finding large induced sparse subgraphs in C>t-free graphs in quasipolynomial time

    Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Mich ał Pilipczuk, and Paweł Rzążewski. Finding large induced sparse subgraphs in C>t-free graphs in quasipolynomial time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Sympo- sium on Theory of Computing, Virtual Event, Italy, June 21-25 , 2021, pages 330–...

    work page 2021

  23. [23]

    Polynomial-time algorithm for maximum weight independent set on P6-free graphs

    Andrzej Grzesik, Tereza Klimošová, Marcin Pilipczuk, and Michał Pilipczuk. Polynomial-time algorithm for maximum weight independent set on P6-free graphs. ACM Trans. Algorithms , 18(1):4:1–4:57, 2022

    work page 2022

  24. [24]

    Po lynomial algorithms for perfect graphs

    Martin Grötschel, Laszlo Lovász, and Alexander Schrijver. Po lynomial algorithms for perfect graphs. In C. Berge and V. Chvátal, editors, Topics on Perfect Graphs, volume 88 of North-Holland Mathematics Studies, pages 325–356. North-Holland, 1984

    work page 1984

  25. [25]

    Problems from the world surrounding perfec t graphs

    András Gyárfás. Problems from the world surrounding perfec t graphs. Applicationes Mathemat- icae, 19(3-4):413–441, 1987

    work page 1987

  26. [26]

    Kang, and Jean-Sébastien Sereni

    Frédéric Havet, Ross J. Kang, and Jean-Sébastien Sereni . Improper coloring of unit disk graphs. Networks, 54(3):150–164, 2009

    work page 2009

  27. [27]

    Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium o n Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1802–1811. SIAM, 2014

    work page 2014

  28. [28]

    Richard M. Karp. Reducibility among combinatorial proble ms. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held Ma rch 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by ...

    work page 1972

  29. [29]

    Feedback vertex set on chordal bipartite graphs

    Ton Kloks, Ching-Hao Liu, and Sheung-Hung Poon. Feedback v ertex set on chordal bipartite graphs. CoRR, abs/1104.3915, 2012

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  30. [30]

    Lima, Martin Milanič, Peter Mursic, Karolina Okra sa, Pawel Rzążewski, and Kenny Štorgel

    Paloma T. Lima, Martin Milanič, Peter Mursic, Karolina Okra sa, Pawel Rzążewski, and Kenny Štorgel. Tree decompositions meet induced matchings: beyond m ax weight independent set. CoRR, abs/2402.15834, 2024

    work page arXiv 2024

  31. [31]

    In dependent set in P5-free graphs in polynomial time

    Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger. In dependent set in P5-free graphs in polynomial time. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Ore gon, USA, January 5-7, 2014 , pages 570–581. SIAM, 2014

    work page 2014

  32. [32]

    Lozin and Dieter Rautenbach

    Vadim V. Lozin and Dieter Rautenbach. Some results on graph s without long induced paths. Inf. Process. Lett., 88(4):167–171, 2003

    work page 2003

  33. [33]

    Lozin and Viktor Zamaraev

    Vadim V. Lozin and Viktor Zamaraev. The structure and the n umber ofP7-free bipartite graphs. Eur. J. Comb., 65:143–153, 2017. 42

    work page 2017

  34. [34]

    Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Parameterized algo- rithms for even cycle transversal. In Martin Charles Golumbic, Michal Stern, Avivit Levy, and Gila Morgenstern, editors, Graph-Theoretic Concepts in Computer Science - 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selct ed Papers...

    work page 2012

  35. [35]

    Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs

    Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs. SIAM J. Discret. Math. , 36(4):2453– 2472, 2022

    work page 2022

  36. [36]

    A tight lower bound for Vertex Planariza tion on graphs of bounded treewidth

    Marcin Pilipczuk. A tight lower bound for Vertex Planariza tion on graphs of bounded treewidth. Discret. Appl. Math., 231:211–216, 2017

    work page 2017

  37. [37]

    Quasi-polynomial-time algorithm for independent set in Pt-free graphs via shrinking the space of induced paths

    Marcin Pilipczuk, Michał Pilipczuk, and Paweł Rzążewski. Quasi-polynomial-time algorithm for independent set in Pt-free graphs via shrinking the space of induced paths. In Hung V iet Le and Valerie King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtu al Conference, January 11-12, 2021, pages 204–209. SIAM, 2021

    work page 2021

  38. [38]

    A polynomial boundon the number of minimal separators and potential maximal cliques inP6-free graphs of bounded clique number

    Marcin Pilipczuk and Paweł Rzążewski. A polynomial boundon the number of minimal separators and potential maximal cliques inP6-free graphs of bounded clique number. CoRR, abs/2310.11573, 2023

    work page arXiv 2023

  39. [39]

    Vapnik and Alexei Ya

    Vladimir N. Vapnik and Alexei Ya. Chervonenkis. On the unif orm convergence of relative fre- quencies of events to their probabilities. Theory of Probability & Its Applications , 16(2):264–280, 1971. 43

    work page 1971