2026-10-07T11:09:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24135 2025-11-12T12:33:29Z ddc:004 open_access

Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás' Path Argument Bourneuf, Romain Masaříková, Jana Nadara, Wojciech Pilipczuk, Marcin long-claw-free graphs extended strip decomposition maximum weight independent set Gyárfás' path three in a tree For a fixed integer t ⩾ 1, a (t-)long claw, denoted S_{t,t,t}, is the unique tree with three leaves, each at distance exactly t from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gyárfás' path argument for S_{t,t,t}-free graphs: given an n-vertex S_{t,t,t}-free graph, one can delete neighborhoods of 𝒪(log n) vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. In this work, we refine the argument of Majewski et al. to its arguably final form: we show that a constant number of neighborhoods suffice. The statement of Majewski et al. is one of the two pillars of a recent quasi-polynomial time algorithm for Maximum Weight Independent Set in S_{t,t,t}-free graphs [Gartland et al., STOC 2024]; our work immediately improves the quasi-polynomial function in the running time bound. Furthermore, our result significantly simplifies known polynomial-time algorithms for Maximum Weight Independent Set in S_{t,t,t}-free graphs with an additional sparsity assumption such as bounded degree or excluding a fixed biclique as a subgraph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Romain Bourneuf and Jana Masaříková and Wojciech Nadara and Marcin Pilipczuk 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.28 urn:nbn:de:0030-drops-241350 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode