Pith. sign in

REVIEW 3 major objections 3 minor 60 references

Induced packing treewidth

T0 review · 3 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read Bounded induced-H-packing treewidth—a tree-decomposition parameter measuring how many anticomplete induced copies of H can meet a bag—yields quasipolynomial-time algorithms for maximum-weight independent set, list 3-coloring, and odd cycle

desk verdict A serious unifying framework for structured tree decompositions with real quasipolynomial algorithms, but the all-cycles separator rests on an unverified external theorem cited only as a YouTube video. read the letter →

arxiv 2607.07595 v2 pith:S22PUGSB submitted 2026-07-08 math.CO cs.DMcs.DS

Amir Nikabadi , Pawe{l} Rzążewski This is my paper · ORCID
classification math.COcs.DMcs.DS MSC 05C8505C6905C38
keywords inducedpackingtreewidthtreedecompositionmaximumweightindependentsetlist3-coloringoddcycletransversalErdős–Pósapropertyquasipolynomialtimeblobgraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper introduces induced-H-packing treewidth, a parameter that assigns to each graph the minimum, over all tree decompositions, of the maximum number of pairwise anticomplete induced copies of graphs from H that intersect a single bag. It generalizes two known parameters: tree-independence number (when H={P1}) and induced matching treewidth (when H={P2}). The authors show that boundedness of this parameter yields quasipolynomial-time algorithms for Maximum-Weight Independent Set when H contains P4, List 3-Coloring when H contains P5, and Odd Cycle Transversal when H contains P3; they also obtain a QPTAS for finding large induced subgraphs of bounded treewidth satisfying a hereditary formula when P3 is present, and a QPTAS for MWIS when H contains all cycles or any path. These results partially answer a recently posed open question about P3- and cycle-packing tree decompositions.

What carries the argument

The central object is the parameter induced-H-packing treewidth, denoted tree-π_H(G): the minimum, over all tree decompositions of G, of the maximum number of pairwise anticomplete induced copies of graphs from H that intersect a common bag. Two workhorses carry the argument: (1) container lemmas that, for a bag B with bounded packing number, enumerate a quasipolynomial-size family of (B,H)-clean induced subgraphs that preserve the existence (or optimal weight) of independent sets or list 3-colorings, and (2) the blob graph G∘, whose vertices are connected vertex sets of G, which maps induced packings to independent sets and preserves bounded tree-π_{P3}. The cycle case also relies on an ind

What would settle it

A counterexample to that Erdős–Pósa claim: construct a graph G and set B with no two anticomplete induced B-cycles, yet every set of fewer than c k^3 vertices fails to hit all B-cycles in the sense that G−N[Y] still contains a B-rooted cycle; if such graphs exist for unbounded k, the O(k^3 log n) separator bound would fail.

Watch

Extended reading notes

Core claim

The central claim is that many classes defined by forbidden induced subgraphs or induced minors can be captured by a single structural parameter: induced-H-packing treewidth. For a fixed family H, the parameter is computed by taking a tree decomposition and, for each bag, counting the largest number of pairwise anticomplete induced copies of graphs from H that all intersect that bag; the width is the minimum of this count over all decompositions. The paper proves that when this parameter is bounded by a constant, a range of problems become tractable in quasipolynomial time: MWIS for H containing P4, List 3-Coloring for H containing P5, Odd Cycle Transversal for H containing P3, and QPTASes f

Load-bearing premise

The cycle part of the dominated-separator theorem rests on an induced Erdős–Pósa property for B-rooted cycles—the claim that the absence of k+1 pairwise anticomplete such cycles forces a hitting set of O(k^3) vertices—which is cited only as an online video rather than a written proof.

Editorial extensions

If this is right

  • Maximum-Weight Independent Set and List 3-Coloring become quasipolynomial-time solvable in graphs of bounded induced-H-packing treewidth when H contains P4 or P5, respectively.
  • Odd Cycle Transversal and (tw≤r,ψ)-MWIS admit quasipolynomial-time approximation schemes when H contains P3.
  • Every graph of bounded tree-π_H admits a balanced separator dominated by O(kt) vertices if H contains a t-vertex path, and by O(k^3 log n) vertices if H contains all cycles.
  • A tree decomposition of induced-H-packing number at most 8k can be computed in time 2^{O(k^2)} n^{O(k)} when it exists, and the parameter is NP-hard to compute exactly.
  • These results partially resolve the previously open question on P3- and cycle-packing treewidth tractability.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The framework likely extends to subdivided claws: the paper conjectures that bounded induced-subdiv(K_{1,3})-packing treewidth makes MWIS tractable, leaving a concrete open direction.
  • If the cited induced Erdős–Pósa property for B-rooted cycles holds with polynomial bounds as stated, the separator results transfer directly to any family containing all cycles; a written proof would solidify this dependence.
  • The container-lemma recursion may be tightenable to polynomial time for specific H, which would answer a natural open question about when quasipolynomial can be improved.
  • The parameter offers a new bridge toward the broader conjectures on induced-minor-free classes, suggesting that separator-and-container techniques could be exported beyond the linear-forest case.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper introduces induced-\mathcal{H}-packing treewidth, a tree-decomposition parameter measuring, for each bag, the maximum size of a family of pairwise anticomplete induced copies of graphs from a fixed family \mathcal{H} that all meet the bag. It observes that this parameter generalizes tree-independence number and induced matching treewidth, and it claims a broad algorithmic program: quasipolynomial-time MWIS when \mathcal{H} contains P_4, quasipolynomial-time List 3-Coloring when \mathcal{H} contains P_5, quasipolynomial-time Odd Cycle Transversal and a QPTAS for hereditary bounded-treewidth CMSO_2 problems when \mathcal{H} contains P_3, and dominated balanced separators (with resulting QPTAS and subexponential algorithms) when \mathcal{H} contains a fixed path or all cycles. The paper also gives an XP approximation algorithm for computing the new parameter and NP-hardness/inapproximability lower bounds. The P_3, P_4, and P_5 algorithm sections and the path-separator lemma are supported by detailed proofs; the all-cycles separator theorem rests on an external result cited only as a video.

Significance. If the main claims hold, this is a valuable unifying framework. The parameter definition is clean and non-circular: it generalizes known parameters, reduces to them in special cases, and connects a broad family of algorithmic results to a single container-plus-recursion template. The paper contains several genuinely useful technical contributions: the MWIS container lemma with a clear branching potential, the modular-decomposition handling of (B,P_4)-clean graphs, the (B,P_5)-clean decomposition for List 3-Coloring, the two-layer reduction for OCT, and the blob-graph stability result. The decomposition approximation and hardness results are also well organized. However, two load-bearing points are not in final verifiable form: the all-cycles separator theorems depend on a theorem cited only as a YouTube video, and the List 3-Coloring container lemma is only sketched. These must be remedied before the central claims can be considered established.

major comments (3)
  1. [§8.2, Theorem 8.2, Lemma 8.3] The all-cycles case of Theorem 1.6 and Corollary 1.7 rests entirely on the induced Erdős–Pósa theorem for B-rooted cycles, stated as Theorem 8.2 and cited only as an online video [3]. This is not a peripheral black box: Lemma 8.3 uses it to produce the O(k^3) set Y, and without that set the weighted-separator induction and the O(k^3 log n) bound do not go through. A published theorem cannot rest on a video citation. Please supply a complete proof of Theorem 8.2, or replace [3] by a written peer-reviewed source, or restrict the claims that depend on it. The footnote asserting equivalence between non-induced (3,B)-cycles and induced B-cycles is also asserted without proof; if the external theorem is used in that translated form, the translation needs a proof.
  2. [§4, Lemma 4.2] Lemma 4.2 is the container lemma for List 3-Coloring and is load-bearing for Theorem 1.3 and hence for the abstract's P_5 claim. However, the proof is explicitly only a sketch. The key branching measure U^* requires a precise invariant after exhaustive application of the reduction rules: one needs a formal argument that at every processed node all lists have size at least 2, that the chosen color i lies in A ∩ L'(x), and that the size of U^* decreases by a constant fraction in both branches even after the reduction rules are re-applied. The sketch asserts these facts but does not prove them. Please provide a full proof or a detailed formal treatment in the paper or an appendix.
  3. [§10.1, Theorem 10.1] The construction in the proof of Theorem 10.1 appears incorrect. After subdividing every edge of a cubic graph 2t times, the set S(v) of vertices at distance t from a core vertex v is an independent set of three vertices: the three chosen vertices are pairwise at distance 2t via v and hence are pairwise non-adjacent. Such a set is not isomorphic to a subdivided claw unless the subdivided claw is a single vertex. Consequently the claimed decomposition with tree-π_H(G')=1 is not justified, and the hardness conclusion over graphs of tree-π_H=1 does not follow. Either replace S(v) by the ball of radius t around v and rework the packing-number verification, or delete/qualify this negative result.
minor comments (3)
  1. [§6.4, proof of Theorem 6.4] The text first sets F(n)=2^{O(log^3 n)} and then concludes F(n)=n^{O(log^2 n)}. This is correct only because 2^{O(log^3 n)}=n^{O(log^2 n)}; the equality should be stated explicitly to avoid the appearance of a mismatch with the theorem statement.
  2. [§3, Lemma 3.2(3)] The proof of the monotonicity tree-π_{P_{t+1}} ≤ tree-π_{P_t} chooses a t-vertex subpath of each path; it should state explicitly that the chosen subpaths remain pairwise anticomplete, since they are subgraphs of pairwise anticomplete paths. The argument is clear but a one-line justification would help.
  3. [References] Reference [3] is a YouTube video. Independent of the major issue, the paper should give a publication venue or arXiv identifier if one becomes available, and should distinguish the video's content from the theorem statement used here.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithmic results are derived from self-contained container lemmas and clearly identified external black boxes, not from assuming the conclusions.

full rationale

Walking the derivation chain, the new parameter tree-pi_H is defined independently, and its coincidences with tree-independence number (H={P1}) and induced matching treewidth (H={P2}) are explicitly presented as special cases rather than as predictions. The container lemmas (4.1, 4.2) assume only pi_H(G,B)<=k and produce (B,H)-clean residual instances by branching; the subsequent MWIS, List 3-Coloring, OCT, and dominated-separator algorithms use those containers plus standard structural lemmas (modular decomposition, the Gyárfás path argument, blob graphs). Theorem 1.8 reduces decomposition computation to the external tree-independence algorithm of Dallard et al. through the proved equality tree-pi_H(G)=tree-alpha(G°_H); this is a computational reduction, not a circular identification. The clearest caveat is Theorem 8.2 (Ahn-Kwon induced Erdős-Pósa property for B-cycles), which is load-bearing for Lemma 8.3 and the all-cycles case of Theorem 1.6 but is cited only as an online video [3], with a brief footnote asserting equivalence between non-induced and induced B-cycles. This is an external verifiability and support gap, and a possible correctness risk, but it is not circularity: the paper neither fits a parameter to the conclusion nor assumes the separator theorem. Self-citations to [30], [31], [47], and [57] are to prior published work invoked as black boxes with stated assumptions, and none reduces the central claims to their own inputs.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces a new graph parameter, induced-H-packing treewidth, but this is a definitional contribution rather than an empirical postulate like a new particle or force; it is anchored by equivalences with tree-independence number and induced matching treewidth. There are no fitted numerical parameters or data-derived constants. The load-bearing external facts are listed as axioms; the most fragile is the video-cited Ahn-Kwon cycle Erdos-Posa theorem.

assumptions (7)
  • standard math Gyárfás path argument: every connected vertex-weighted graph has an induced path starting at a given vertex whose closed neighborhood is a balanced separator.
    Used in Lemma 6.1 for List 3-Coloring residual instances and in Lemma 8.1 for the path separator theorem; cited from [17,14,35], not proved in this paper.
  • standard math Edwards' theorem: list coloring with lists of size at most 2 reduces to 2-SAT and is polynomial-time solvable.
    Core solvability step in Lemma 6.3 and the List 3-Coloring algorithm; cited to [24].
  • domain assumption Ahn-Kwon theorem: B-rooted induced cycles satisfy an induced Erdos-Posa property; if no k+1 pairwise anticomplete B-cycles exist, then O(k^3) vertices Y satisfy that G-N[Y] has no B-rooted cycle.
    Load-bearing in Lemma 8.3 and Theorem 1.6 for the all-cycles case; cited only to an online video [3] rather than a written paper.
  • standard math Dallard-Fomin-Golovach-Korhonen-Milanič algorithm: in time 2^{O(k^2)} n^{O(k)}, either output a tree decomposition with independence number at most 8k or report tree-alpha(G) > k.
    Used in Theorem 1.8 to compute induced-H-packing decompositions by reducing to tree-independence number; cited to [21].
  • standard math Standard tree-decomposition separator lemma: every vertex-weighted graph with a tree decomposition has a bag that is a balanced separator.
    Used to find the central bag B in Theorems 1.2-1.6; cited to [20, Lemma 7.19].
  • standard math Classical modular decomposition theorem: every graph has a linear-size modular decomposition tree whose quotient graphs are complete, edgeless, or prime.
    Used in Lemma 5.1 and the P4/MWIS proof; cited to [36].
  • domain assumption Blob-graph QPTAS framework of Gartland et al.: for hereditary classes closed under blob graph, hereditary CMSO2 (tw<=r, psi)-MWIS has a QPTAS.
    Used to prove Theorem 1.5 for bounded tree-pi_{P3}; imported from [30,31], not proved here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Induced packing treewidth." pith.science (2026). https://pith.science/paper/S22PUGSB

@misc{pith2026260707595,
  author       = {Pith},
  title        = {Pith review of: Induced packing treewidth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S22PUGSB}},
  note         = {Machine review of arXiv:2607.07595}
}
abstract

In this paper, we introduce a framework that aims to unify classes defined by forbidden induced subgraphs or induced minors with classes defined by the existence of certain structured tree decompositions. Let $\mathcal{H}$ be a fixed family of graphs. We define \emph{induced-$\mathcal{H}$-packing treewidth}, a tree-decomposition-based graph parameter that, for each bag, measures the maximum number of pairwise anticomplete induced copies of graphs from $\mathcal{H}$ intersecting that bag. This notion generalizes some previously studied parameters: when $\mathcal{H}=\{P_1\}$, it is equivalent to tree-independence number, and when $\mathcal{H}=\{P_2\}$, it is equivalent to induced matching treewidth. We show that bounded induced-$\mathcal{H}$-packing treewidth yields new algorithmic consequences for a range of choices of $\mathcal{H}$. In particular, we prove the following results for graphs of bounded induced-$\mathcal{H}$-packing treewidth. Our results partially answer and substantially extend a question of Bodlaender, Fomin, and Korhonen [SODA~2026] on the tractability of \textsc{MWIS} for graphs of bounded induced-$\mathcal{H}$-packing treewidth for $\mathcal{H}=\{P_3\}$ and for $\mathcal{H}$ equal to the family of all cycles.

Review history (4 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 2 canonical work pages

  1. [3]

    Ahn and O.-j

    J. Ahn and O.-j. Kwon. A coarse Erdős–Pósa theorem for constrained cycles.https://www. youtube.com/watch?v=XIBsf0AxiEA, 2026. Online video; accessed 2026-06-10

    2026

  2. [1]

    Abrishami, M

    T. Abrishami, M. Briański, J. Czyżewska, R. McCarty, M. Milanič, P. Rzążewski, and B. Walczak. Excluding a clique or a biclique in graphs of bounded induced matching treewidth.SIAM Journal on Discrete Mathematics, 39(2):1189–1200, 2025

    2025

  3. [2]

    Abrishami, M

    T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzążewski, and P. D. Seymour. Induced subgraphs of bounded treewidth and the container method.SIAM J. Comput., 53(3):624–647, 2024. URL: https://doi.org/10.1137/20m1383732,doi:10.1137/20M1383732

    doi:10.1137/20m1383732 2024

  4. [4]

    V. E. Alekseev. The effect of local constraints on the complexity of determination of the graph independence number.Combinatorial-algebraic methods in applied mathematics, pages 3–13, 1982

    1982

  5. [5]

    Bacsó, D

    G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Z. Tuza, and E. J. van Leeuwen. Subexponential- time algorithms for Maximum Independent Set inP t-free and broom-free graphs.Algorith- mica, 81(2):421–438, 2019. URL:https://doi.org/10.1007/s00453-018-0479-5,doi:10.1007/ S00453-018-0479-5

    doi:10.1007/s00453-018-0479-5 2019

  6. [6]

    H. L. Bodlaender, F. V. Fomin, and T. Korhonen. Finding sparse induced subgraphs on graphs of bounded induced matching treewidth. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2043–2068. SIAM, 2026

    2026

  7. [7]

    Bonamy, É

    M. Bonamy, É. 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.J. Comb. Theory B, 167:215–249, 2024. URL:https://doi.org/10.1016/j.jctb.2024.03.003,doi:10. 1016/J.JCTB.2024.03.003

    doi:10.1016/j.jctb.2024.03.003 2024

  8. [8]

    Bonnet, J

    É. 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. In P. Fraigniaud, 38 INDUCED PACKING TREEWIDTH editor,20th Scandinavian Symposium on Algorithm Theory, SW AT 2026, Copenhagen, Denmark, June 17-19, 2026, volume 370 ofLIPIcs, pages 9:1–9:...

    doi:10.4230/lipics.swat.2026.9 2026

Show all 60 references
  1. [9]

    Bonnet, J

    É. Bonnet, J. Duron, C. Geniet, S. Thomassé, and A. Wesolek. Maximum independent set when excluding an induced minor:K 1 +tK 2 andtC 3⊎C 4.Algorithmica, 88(1):16, 2026. URL:https: //doi.org/10.1007/s00453-025-01356-2,doi:10.1007/S00453-025-01356-2

    2026 doi

  2. [10]

    Bonomo, M

    F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong. Three-coloring and list three-coloring of graphs without induced paths on seven vertices.Comb., 38(4):779–801, 2018. URL:https://doi.org/10.1007/s00493-017-3553-8,doi:10.1007/S00493-017-3553-8

    2018 doi

  3. [11]

    Brandstädt and R

    A. Brandstädt and R. Mosca. Maximum weight independent set forℓ-claw-free graphs in polynomial time.Discrete Applied Mathematics, 237:57–64, 2018. URL:https://www.sciencedirect.com/ science/article/pii/S0166218X1730553X,doi:10.1016/j.dam.2017.11.029

    2018 doi

  4. [12]

    Cameron and P

    K. Cameron and P. Hell. Independent packings in structured graphs.Mathematical programming, 105(2):201–213, 2006

    2006

  5. [13]

    Chalermsook, M

    P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai, and L. Tre- visan. From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more.SIAM J. Comput., 49(4):772–810, 2020.doi:10.1137/18M1166869

    2020 doi

  6. [14]

    Chudnovsky, J

    M. Chudnovsky, J. P. Gollin, M. Krnc, and M. Milanič. Dominated balanced separators in wheel- induced-minor-free graphs.arXiv preprint arXiv:2512.12329, 2025.arXiv:2512.12329,doi:10. 48550/arXiv.2512.12329

    2025 doi

  7. [15]

    Chudnovsky, S

    M. Chudnovsky, S. Huang, S. Spirkl, and M. Zhong. List 3-coloring graphs with no inducedP6 +rP 3. Algorithmica, 83(1):216–251, 2021. URL:https://doi.org/10.1007/s00453-020-00754-y,doi: 10.1007/S00453-020-00754-Y

    2021 doi

  8. [16]

    Chudnovsky, R

    M. Chudnovsky, R. McCarty, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Sparse induced sub- graphs inP 6-free graphs.ACM Trans. Algorithms, 22(2):16:1–16:45, 2026.doi:10.1145/3785003

    2026 doi

  9. [17]

    Chudnovsky, M

    M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé. Quasi-polynomial time approxima- tion schemes for the Maximum Weight Independent Set problem inH-free graphs.SIAM Journal on Computing, 53(1):47–86, 2024.arXiv:1907.04585,doi:10.1137/20M1333778

    2024 arXiv

  10. [18]

    Chudnovsky, A

    M. Chudnovsky, A. E. S., and D. Lokshtanov. (Treewidth, clique)-boundedness and poly-logarithmic tree-independence.CoRR, abs/2510.15074, 2025. URL:https://arxiv.org/abs/2510.15074, arXiv:2510.15074

    2025 arXiv

  11. [19]

    Chudnovsky and P

    M. Chudnovsky and P. D. Seymour. Claw-free graphs. V. Global structure.J. Comb. Theory B, 98(6):1373–1410, 2008. URL:https://doi.org/10.1016/j.jctb.2008.03.002,doi:10.1016/J. JCTB.2008.03.002

    2008 doi

  12. [20]

    Cygan, F

    M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.Parameterized Algorithms, volume 5. Springer, 2015

    2015

  13. [21]

    Dallard, F

    C. Dallard, F. V. Fomin, P. A. Golovach, T. Korhonen, and M. Milanič. Computing tree decompo- sitions with small independence number.ACM Transactions on Algorithms, 22(1):1–25, 2025

    2025

  14. [22]

    Dallard, M

    C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. II. Tree-independence number.Journal of Combinatorial Theory, Series B, 164:404–442, 2024

    2024

  15. [23]

    Dallard, M

    C. Dallard, M. Milanič, and K. Štorgel. Treewidth versus clique number. III. tree-independence number of graphs with a forbidden structure.J. Comb. Theory B, 167:338–391, 2024. URL:https: //doi.org/10.1016/j.jctb.2024.03.005,doi:10.1016/J.JCTB.2024.03.005

    2024 doi

  16. [24]

    K. Edwards. The complexity of colouring problems on dense graphs.Theoretical Computer Science, 43:337–343, 1986

    1986

  17. [25]

    Emden-Weinert, S

    T. Emden-Weinert, S. Hougardy, and B. Kreuter. Uniquely colourable graphs and the hardness of colouring graphs of large girth.Comb. Probab. Comput., 7(4):375–386, 1998. URL:http:// journals.cambridge.org/action/displayAbstract?aid=46667

    1998

  18. [26]

    Galby, P

    E. Galby, P. T. Lima, A. Munaro, and A. Nikabadi. Maximum listr-colorable induced subgraphs in kp3-free graphs. In A. Benoit, H. Kaplan, S. Wild, and G. Herman, editors,33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025, volume 351 of...

    2025 doi

  19. [27]

    M. R. Garey, D. S. Johnson, and L. J. Stockmeyer. Some simplified np-complete graph problems. Theor. Comput. Sci., 1(3):237–267, 1976.doi:10.1016/0304-3975(76)90059-1

    1976 doi

  20. [28]

    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, 2023

    2023

  21. [29]

    Gartland and D

    P. Gartland and D. Lokshtanov. Independent set onPk-free graphs in quasi-polynomial time. In S. Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 613–624. IEEE, 2020.doi:10.1109/FOCS46700. 2020.00063

    2020

  22. [30]

    Gartland, D

    P. Gartland, D. Lokshtanov, T. Masařík, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Maxi- mum weight independent set in graphs with no long claws in quasi-polynomial time. In B. Mohar, I. Shinkar, and R. O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theo...

    2024

  23. [31]

    Gartland, D

    P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Finding large induced sparse subgraphs inC >t -free graphs in quasipolynomial time. In S. Khuller and V. V. Williams, editors,STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Ev...

    2021

  24. [32]

    Gartland, D

    P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Finding large induced sparse subgraphs inC >t-free graphs in quasipolynomial time. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 330–341, 2021

    2021

  25. [33]

    Groenland, K

    C. Groenland, K. Okrasa, P. Rzążewski, A. D. Scott, P. D. Seymour, and S. Spirkl.H-colouring Pt-free graphs in subexponential time.Discret. Appl. Math., 267:184–189, 2019. URL:https:// doi.org/10.1016/j.dam.2019.04.010,doi:10.1016/J.DAM.2019.04.010

    2019 doi

  26. [34]

    Grzesik, T

    A. Grzesik, T. Klimošová, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithm for maximum weight independent set onP6-free graphs.ACM Trans. Algorithms, 18(1):4:1–4:57, 2022.doi:10. 1145/3414473

    2022

  27. [35]

    A. Gyárfás. Problems from the world surrounding perfect graphs.Applicationes Mathematicae, 19(3- 4):413–441, 1987

    1987

  28. [36]

    Habib and C

    M. Habib and C. Paul. A survey of the algorithmic aspects of modular decomposition.Computer Science Review, 4(1):41–59, 2010

    2010

  29. [37]

    J. Håstad. Clique is hard to approximate withinn1−ε.Electron. Colloquium Comput. Complex., TR97, 1997. URL:https://eccc.weizmann.ac.il/eccc-reports/1997/TR97-038/index.html, arXiv:TR97-038

    1997

  30. [38]

    R. B. Hayward, S. Hougardy, and B. A. Reed. Polynomial time recognition of P4-structure. In D. Eppstein, editor,Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 382–389. ACM/SIAM, 2002. URL: http:/...

    2002

  31. [39]

    Hilaire, M

    C. Hilaire, M. Milanič, and Ð. Vasič. Treewidth versus Clique Number. V. Further Connections with Tree-Independence Number.CoRR, abs/2505.12866, 2025. URL:https://arxiv.org/abs/2505. 12866,arXiv:2505.12866

    2025 arXiv

  32. [40]

    C. T. Hoàng, M. Kamiński, V. V. Lozin, J. Sawada, and X. Shu. Decidingk-colorability ofP5-free graphs in polynomial time.Algorithmica, 57(1):74–81, 2010. URL:https://doi.org/10.1007/ s00453-008-9197-8,doi:10.1007/S00453-008-9197-8

    2010 doi

  33. [41]

    I. Holyer. The NP-completeness of edge-coloring.SIAM J. Comput., 10(4):718–720, 1981.doi: 10.1137/0210055

    1981 doi

  34. [42]

    Impagliazzo, R

    R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001.doi:10.1006/jcss.2001.1774

    2001

  35. [43]

    R. M. Karp. Reducibility among combinatorial problems. In50 Years of Integer Programming 1958- 2008: from the Early Years to the State-of-the-Art, pages 219–241. Springer, 2009

    1958

  36. [44]

    S. Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. InProceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pages 600–609. IEEE Computer Society, 2001.doi:10.1109/SFCS.2001.959936

    2001

  37. [45]

    Klimošová, J

    T. Klimošová, J. Malík, T. Masařík, J. Novotná, D. Paulusma, and V. Slívová. Colouring Pr +P s-free graphs.Algorithmica, 82(7):1833–1858, 2020. URL:https://doi.org/10.1007/ s00453-020-00675-w,doi:10.1007/S00453-020-00675-W. 40 INDUCED PACKING TREEWIDTH

    2020 doi

  38. [46]

    Leven and Z

    D. Leven and Z. Galil. NP completeness of finding the chromatic index of regular graphs.J. Algo- rithms, 4(1):35–44, 1983.doi:10.1016/0196-6774(83)90032-9

    1983 doi

  39. [47]

    P. T. Lima, M. Milanič, P. Muršič, K. Okrasa, P. Rzążewski, and K. Štorgel. Tree decomposi- tions meet induced matchings: Beyond max weight independent set. In T. M. Chan, J. Fischer, J. Iacono, and G. Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Roy...

    2024 doi

  40. [48]

    B. Lin, X. Ren, Y. Sun, and X. Wang. Improved hardness of approximatingk-Clique under ETH. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 285–306. IEEE, 2023.doi:10.1109/FOCS57990.2023.00025

    2023

  41. [49]

    Lokshtanov, M

    D. Lokshtanov, M. Pilipczuk, and P. Rzążewski. Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number.CoRR, abs/2601.15861, 2026. URL:https:// doi.org/10.48550/arXiv.2601.15861,arXiv:2601.15861,doi:10.48550/ARXIV.2601.15861

    2026 doi

  42. [50]

    D.Lokshtanov, M.Vatshelle, andY.Villanger.IndependentsetinP 5-freegraphsinpolynomialtime. In C. Chekuri, editor,Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 570–581. SIAM, 2014. doi...

    2014 doi

  43. [51]

    V. V. Lozin and M. Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.Journal of Discrete Algorithms, 6(4):595–604, 2008

    2008

  44. [52]

    G. J. Minty. On maximal independent sets of vertices in claw-free graphs.Journal of Combinatorial Theory, Series B, 28(3):284–304, 1980.doi:10.1016/0095-8956(80)90074-X

    1980 doi

  45. [53]

    A. Munaro. On line graphs of subcubic triangle-free graphs.Discrete Mathematics, 340(6):1210– 1226, 2017.doi:10.1016/j.disc.2017.01.006

    2017 doi

  46. [54]

    Nguyen, A

    T. Nguyen, A. D. Scott, and P. D. Seymour. Induced paths in graphs without anticomplete cycles. J. Comb. Theory B, 164:321–339, 2024. URL:https://doi.org/10.1016/j.jctb.2023.10.003, doi:10.1016/J.JCTB.2023.10.003

    2024 doi

  47. [55]

    Novotná, K

    J. Novotná, K. Okrasa, M. Pilipczuk, P. Rzążewski, E. J. van Leeuwen, and B. Wal- czak. Subexponential-time algorithms for finding large induced sparse subgraphs.Algorithmica, 83(8):2634–2650, 2021. URL:https://doi.org/10.1007/s00453-020-00745-z,doi:10.1007/ S00453-020-00745-Z

    2021 doi

  48. [56]

    Paesani, D

    G. Paesani, D. Paulusma, and P. 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. URL: https://doi.org/10.1137/22m1468864,doi:10.1137/22M1468864

    2022 doi

  49. [57]

    Pilipczuk, M

    M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Quasi-polynomial-time algorithm for independent set inP t-free graphs via shrinking the space of induced paths. InSymposium on Simplicity in Algorithms (SOSA), pages 204–209. SIAM, 2021

    2021

  50. [58]

    S.Poljak.Anoteonstablesetsandcoloringsofgraphs.Commentationes Mathematicae Universitatis Carolinae, 15:307–309, 1974

    1974

  51. [59]

    N. Sbihi. Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile. Discrete Mathematics, 29(1):53–76, 1980.doi:10.1016/0012-365X(80)90174-8

    1980 doi

  52. [60]

    N. Yolov. Minor-matching hypertree width. InProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 219–233. SIAM, 2018

    2018

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.