Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument
Romain Bourneuf, Jana Masaříková, Wojciech Nadara, Marcin Pilipczuk · 2025
Read Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument by Romain Bourneuf, Jana Masaříková, Wojciech Nadara, Marcin Pilipczuk (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13907.txt.
Introduction
Romain Bourneuf and co-authors sharpen a math result about graphs with no long claw shapes. A claw here is a tree with three arms, each the same length, joined at one hub. Their 2025 work builds on an older path argument used to split such graphs into small parts. That split helps design fast-ish methods for hard graph tasks.
Past work showed that removing the zones around a modest set of points leaves parts of much smaller size. The new proof trims that set down to a fixed, small count that does not grow with the graph. A tighter split of this kind can feed straight into quicker methods for tasks like picking the best set of free points.
Catalog record
| CREATOR | Romain Bourneuf, Jana Masaříková, Wojciech Nadara, Marcin Pilipczuk |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13907
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument Romain Bourneuf, Jana Masaříková, Wojciech Nadara, Marcin Pilipczuk Abstract For a fixed integer t ⩾ 1 t\geqslant 1 , a ( t t -)long claw , denoted S t , t , t S_{t,t,t} , is the unique tree with three leaves, each at distance exactly t 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 S_{t,t,t} -free graphs: given an n n -vertex S t , t , t S_{t,t,t} -free graph, one can delete neighborhoods of 𝒪 ( log n ) \mathcal{O}(\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. This statement has proven to be very useful in designing quasi-polynomial time algorithms for Maximum Weight Independent Set and related problems in S t , t , t S_{t,t,t} -free graphs. In this work we refine the argument of Majewski et al. and show that a constant number of neighborhoods suffice. 1 Introduction The Maximum Weight Independent Set ( MWIS ) problem is a fundamental problem in combinatorial optimization, where the objective is to find an independent set of vertices in a graph such that the sum of their weights is maximized. The complexity of MWIS significantly varies depending on the structure of the input graph. Some graph classes allow for polynomial-time solutions (e.g., chordal graphs), while in general graphs the problem is NP-hard and hard to approximate within an n^{1-\varepsilon} factor [ 26 , 19 ] . A crucial research direction involves identifying graph classes where the absence of specific substructures simplifies the MWIS problem. This leads to the study of hereditary graph classes—those closed under vertex deletion. Equivalently, they can be defined by a list of forbidden induced subgraphs. In particular, H -free graphs – graphs that do not contain a specific graph H as an induced subgraph – are of significant interest. As observed by Alekseev in the 1980s [ 5 , 6 ] , the problem of MWIS remains NP-hard in H -free graphs for most graphs H : MWIS remains NP-hard unless every connected component of H is either a path or a subdivided claw (three paths connected via a vertex). Moreover, it cannot even be solved in subexponential time, unless the Exponential-Time Hypothesis fails. Thus, significant attention has been devoted to P_{t} -free graphs (graphs excluding a path on t vertices) and to S_{t,t,t} -free graphs (graphs excluding a tree with three leaves connected to the root by paths of length t ). The class of P_{4} -free graphs (also known as cographs) is well-structured and many problems, including MWIS , are polynomial-time solvable in it. Similarly, MWIS is polynomial-time solvable in S_{1,1,1} -free graphs [ 23 , 25 ] (also known as claw-free graphs). For the latter, claw-free graphs are closely related to line graphs, and finding a maximum-weight independent set in a line graph corresponds to finding a maximum-weight matching. The next smallest subdivided claw is S_{2,1,1} (also known as the fork), for which a polynomial algorithm was shown by Alekseev [ 7 ] in 2004. However, moving further is far from being trivial. Currently, S_{1,2,2} is the smallest open case where the polynomiality of MWIS has not been confirmed. In 2014, Lokshtanov, Vatshelle, and Villanger [ 21 ] showed that MWIS is solvable in polynomial time on P_{5} -free graphs using a framework of potential maximal cliques. The result was extended to P_{6} -free graphs by Grzesik, Klimošová, Ma. Pilipczuk, and Mi. Pilipczuk in 2019 [ 16 ] . The case of P_{7} -free graphs remains open. Several related partial results have been obtained, see for instance [ 2 , 4 ] . In 2020, in a breakthrough result, Gartland and Lokshtanov [ 13 ] obtained a quasipolynomial-time algorithm for MWIS in P_{t} -free graphs. The result later got significantly simplified by Pilipczuk, Pilipczuk, and Rzążewski [ 24 ] (but still quasipolynomial time) and generalized to a larger class of problems and to C_{>t} -free graphs (graphs without induced cycle of length more than t ) [ 15 ] . In S_{t,t,t} -free graphs several partial results were obtained. Abrishami, Chudnovsky, Dibek, and Rzążewski announced a polynomial-time algorithm for MWIS in S_{t,t,t} -free graphs of bounded degree [ 1 ] that got later improved [ 3 ] where the same set of authors and Pilipczuk also provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph. However, much less was known for the general cases (even for a specific small t ) up until recently. In 2023, another breakthrough, a quasipolynomial algorithm for S_{t,t,t} -free graphs, was presented by Gartland, Lokshtanov, Masařík, Pilipczuk, Pilipczuk, and Rzążewski [ 14 ] . This progress corroborates the conjecture that MWIS is polynomial-time solvable in H -free graphs for all the open cases left by the original hardness reductions, that is, whenever H is a forest whose every connected component has at most three leaves. The work [ 14 ] is built upon two pillars. The first one is the branching strategy similar to the first P_{t} -free paper [ 13 ] . The second pillar is a work [ 22 ] that gives a structural result for S_{t,t,t} -free graphs that is an analog of the Gyárfás’ path argument from P_{t} -free graphs. In this work, we improve the main result of [ 22 ] to a form with near optimal parameter dependency. Before we state the result formally, let us discuss the relevant results and techniques. Firstly, we return to P_{t} -free graphs. In the 1980s, Gyárfás showed that for every fixed t the class of P_{t} -free graphs is \chi -bounded [ 17 , 18 ] . Bacsó, Lokshtanov, Marx, Pilipczuk, Tuza, and van Leeuwen [ 8 ] gave a subexponential-time algorithm for MWIS in P_{t} -free graphs, using the following important corollary of the Gyárfás’ path argument. Theorem 1 . Given an n -vertex graph G with nonnegative vertex weights, one can in polynomial time find an induced path Q in G such that every connected component of G-N[V(Q)] has weight at most half of the total weight of V(G) . Observe that in P_{t} -free graphs, Q contains at most t-1 vertices. In particular, having connected components of multiplicatively smaller size after removing the neighborhood of a constant number of vertices became very useful in the recursive approach. For the progress in general S_{t,t,t} -free graphs, the paper [ 22 ] shows that the notion of an extended strip decomposition , developed by Chudnovsky and Seymour in their project to understand claw-free graphs [ 11 ] , became useful as an analog of the Gyárfás’ path argument. For a formal definition of extended strip decomposition, we refer to Section 2 . For an intuition to develop, we remark that in an extended strip decomposition of a graph, we can distinguish particles (specific