WorksComputer Science
Max Weight Independent Set in graphs with no long claws nor large induced bicliques
Abstract
The complexity of Max Weight Independent Set (MWIS) in graphs excluding a fixed subdivided claw is one of the central open problems in algorithmic graph theory. We show that MWIS can be solved in polynomial time in graphs excluding a fixed subdivided claw and a fixed biclique as an induced subgraph. This strengthens a result of Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [ACM TALG 2026] who showed an analogous result, but under a stronger assumption that some biclique is excluded as a subgraph.
Introduction
Maximum Weight Independent Set (MWIS) is one of the fundamental problems in algorithmic graph theory. Given a graph with nonnegative vertex weights, the task is to find a set of pairwise nonadjacent vertices (i.e., an independent set) of maximum total weight. The unweighted version of this problem is equivalent, by graph complementation, to Clique, one of Karp’s 21 NP-hard problems [19]. Nevertheless, MWIS admits polynomial-time algorithms in many important graph classes, including perfect graphs [16], claw-free graphs [13, 26, 29], and circle graphs (these are the intersection graphs of chords of a circle) [30].
We are interested in the complexity of MWIS in graph classes defined by forbidden induced subgraphs. For two graphs and , the graph is -free if contains no induced subgraph isomorphic to . More generally, is -free if it is -free for every . For , let denote the path on vertices, i.e., of length . For , the subdivided claw is obtained from three paths of lengths by identifying one endpoint of each path into a single vertex. In particular, is the three-leaf star, also known as the claw. Let be the family of all graphs such that each component of is a subcubic tree with at most three leaves, or equivalently, a path or a subdivided claw.
Alekseev [4] showed that, for every fixed , even the problem of finding an independent set of maximum size (this is a special case of MWIS with all equal vertex weights) remains NP-hard in -free graphs. For , polynomial-time algorithms are known only in special cases. Notable examples include -free graphs, by Lokshtanov, Vatshelle, and Villanger [22]; -free graphs, by Grzesik, Klimošová, Pilipczuk, and Pilipczuk [17]; and fork-free graphs, by Lozin and Milanič [23], where the fork is . There are also nontrivial tractable cases with disconnected forbidden graphs [6, 8].
Interestingly, for every , MWIS in -free graphs can be solved in quasipolynomial time. This was first established by Gartland and Lokshtanov [14] (see also [28]) for the case that is a path, and then extended to general by Gartland, Lokshtanov, Masařík, Pilipczuk, Pilipczuk, and Rzążewski [15]. Whether these cases all admit polynomial-time algorithms remains wide open.
This motivates studying -free graphs under additional restrictions. For example, polynomial-time algorithms for MWIS are known for graphs that exclude and some small graphs [7, 24, 27]. Recently, MWIS was shown to be polynomial-time-solvable in -free graphs of bounded clique number by Chudnovsky, Czyżewska, Kluk, Pilipczuk, and Rzążewski [9]. Another direction is to impose sparsity conditions. For every fixed and integer , Abrishami, Chudnovsky, Dibek, and Rzążewski [3] gave a polynomial-time algorithm for MWIS in -free graphs of maximum degree at most . This was strengthened by Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [1], who replaced the degree bound with the assumption that a fixed biclique is excluded as a subgraph, not necessarily induced. In this paper we further generalize these results by requiring only that a fixed biclique be excluded as an induced subgraph.
Theorem 1.1. For every fixed and , there is a polynomial-time algorithm which, given an -free graph and a weight function , returns a maximum-weight independent set in .
We emphasize that, by the celebrated Kővári–Sós–Turán theorem [20], excluding a fixed biclique as a subgraph forces the number of edges to be subquadratic, and in -free graphs, the number of edges becomes even linear the result of Kuhn and Osthus [21]. Our setting permits quadratically many edges, so the algorithm must also accommodate dense graphs.
Our proof combines the algorithmic use of extended strip decompositions developed by Chudnovsky, Pilipczuk, Pilipczuk, and Thomassé [11] with the boundary formulation of Abrishami et al. [1]. An extended strip decomposition allows solutions on overlapping pieces, called particles, to be assembled in polynomial time. The key is to control the independence number of separators and boundaries, which may contain arbitrarily many vertices.
Bounding the independence number is sufficient for our purposes: every independent set contains only a bounded number of vertices from a set of bounded independence number, so all possible intersections of a solution with such a set can be enumerated in polynomial time. Combining structural results of Hajebi and Spirkl [18] with those of Bourneuf, Masariková, Nadara, and Pilipczuk [5], we show how to efficiently find, in a graph excluding a fixed subdivided claw and a fixed biclique, a set of bounded independence number whose deletion leaves a graph with an extended strip decomposition in which every particle contains at most half of the vertices from a prescribed set. We use such decompositions recursively: from each particle, we remove a set of bounded independence number and recurse on the components of the remaining graph. An appropriate choice of the prescribed set ensures that the recursion depth is logarithmic. For each such component, we consider every possible intersection of a solution with its boundary, which is a certain set of neighbors of the component, and compute the best way to extend it inside the component. A new ingredient is a bound on the independence number of these boundaries, which guarantees that only polynomially many such intersections need to be considered. As each vertex belongs to only a bounded number of the components considered in a single recursive call, the total running time is polynomial. Finally, if has several components, we again use the machinery of Hajebi and Spirkl [18] to find a set of bounded independence number that intersects every induced copy of a sufficiently long subdivided claw; deleting this set reduces the problem to graphs excluding a single subdivided claw.
Preliminaries
Weights. Let be a graph and let be a weight function on the vertices of . A vertex-weighted graph is a pair . We also use for its restriction to any induced subgraph of . For a set , we define , and we write . Arithmetic operations and comparisons of weights take constant time.
In the paper we will use two types of weight functions: one coming from the input of MWIS, and another indicating some “important” vertices in the graph. To avoid confusion, the second function will be called a mass function and typically denoted by . Usually, the mass will be defined for a subset as if and otherwise. We will call such a function indicator mass function of .
Graph theory. For two graphs and , we denote by the disjoint union of and . For , let be the set of neighbors of , i.e., vertices outside with a neighbor in , and write . Two sets are anticomplete if they are disjoint and no edge joins them. For a graph , by we denote the independence number of , i.e., the size of a maximum independent set in . For a vertex-weighted graph , by we denote the maximum weight of an independent set in with respect to . If is clear from the context, for we will write and instead of and , respectively.
Paths in graphs. Let be a graph and let , be disjoint subsets of . By –-path we mean a path in with one endpoint in , the other endpoint in , and all internal vertices in . An –-separator is a set that intersects all –-paths in .
Extended strip decompositions. We follow the notation of [15, 25]. A triangle in a graph is a set of three distinct, pairwise adjacent vertices. For a graph , by we denote the set of triangles in . We write for a triangle . An extended strip decomposition of a graph is a pair that consists of:
a simple graph called the host,
a vertex atom for every ,
an edge atom for every , and its subsets called interfaces, and
a triangle atom for every ,
which have the following properties (empty sets are allowed):
The family is a partition of .
For every and every distinct , the set is complete to (i.e., all possible edges between these two sets exist).
Every is contained in one of the atoms for , or is as follows:
for some and , or
for some , or
and for some .
A schematic picture of an extended strip decomposition of a graph is shown in Figure 1.
Figure 1. A graph (top) and a schematic view of an extended strip decomposition of a graph . Green areas depict the sets . Solid line indicates that all edges between two sets exist. Dashed line denotes that edges might exist. Picture from [15], courtesy of the authors.
An extended strip decomposition is rigid if for every , the sets and are nonempty, and for every isolated , the vertex atom is nonempty.
For an extended strip decomposition of a graph , we identify five types of particles.
vertex particle: for each ,
edge interior particle: for each ,
half-edge particle: for each ,
full edge particle: for each ,
triangle particle: for each .
Given a mass function on , a decomposition of an induced subgraph of is *balanced for if every particle satisfies .
Let us conclude with listing some straightforward properties of extended strip decompositions that will be used in the paper. The first two follow directly from the definition of extended strip decompositions, and the last one is shown in [25 Observation 5].
Proposition 2.1. The following hold.
Let be a graph, let be an extended strip decomposition of , and let . By restricting to , we obtain an extended strip decomposition of , with every particle replaced by its intersection with .
Let be two graphs on disjoint vertex sets, let and be extended strip decompositions of and , respectively. Then, by taking the disjoint union of and and the union of and , we obtain an extended strip decomposition of .
If is a rigid extended strip decomposition of , then and .
The main algorithmic application of extended strip decompositions is that, given an extended strip decomposition of , one can reduce computing to solving MWIS in particles of .
Theorem 2.2 (Chudnovsky, Pilipczuk, Pilipczuk, and Thomassé [11 Section 3.3]). Given a weighted graph , an extended strip decomposition of , and the value for every particle , one can compute in time polynomial in .
Auxiliary tools
In this section we develop a number of tools that will be used in the proof of Theorem 1.1.
Hitting sets of small independence number
For a graph and an integer , a -system in is a family of nonempty vertex sets of , each of size at most ; the family itself may be empty. A set hits a family if it intersects every member. Note that an empty set system is hit by the empty set. Hajebi and Spirkl [18] proved that in graphs excluding a fixed induced biclique, -systems admit a certain Erdős–Pósa-type property: either we can find many pairwise anticomplete members of the system, or a hitting set of small independence number.
Lemma 3.1 (Hajebi and Spirkl [18 Lemma 6.2]). For , there is a computable constant such that, for every -free graph and every -system in , one of the following holds:
there is a hitting set for with ; or
there are pairwise anticomplete members of .
Lemma 3.2 (Hajebi and Spirkl [18 Theorem 3.1]). For every , there are computable constants and such that, for every -free graph and every -system in , one of the following holds:
there is a hitting set for with ; or
there are anticomplete and an –-separator with .
Lemma 3.3 (Algorithmic Lemma 3.1). For fixed , there is a computable constant and a polynomial-time algorithm which, given a -system in a -free graph , returns either:
a hitting set for with ; or
pairwise anticomplete members of .
Proof. Enumerate all -tuples of members of and return an anticomplete tuple if it exists. This can be done in polynomial time, as both and are fixed.
Otherwise, Lemma 3.1 guarantees a hitting set of independence number at most . Without loss of generality we may assume that this hitting set is contained in . Solve the rational feasibility program
This linear program has a solution: indeed, the indicator vector of the guaranteed hitting set satisfies every constraint. Take .
By the second family of constraints, for every , we have , and hence . On the other hand, , as otherwise we would have an independent set of size , and then , violating the last constraint of the program. Thus we can set .
Note that the number of constraints is polynomial in , as and are constants. As linear programs can be solved in polynomial time, the proof is complete. □
Lemma 3.4 (Algorithmic Lemma 3.2). For every , there are constants and and a polynomial-time algorithm that, given an -free graph and a -system in , returns either:
a hitting set for with ; or
two anticomplete members and an –-separator with .
Proof. Define the following constants depending only on :
Apply Lemma 3.3 to with parameters . If the call returns the first outcome, i.e., a hitting set with independence number at most , we return it as the first outcome.
Thus, suppose that the application of Lemma 3.3 returns a subfamily consisting of pairwise anticomplete members of . Every hitting set for has independence number at least , as the sets in are pairwise anticomplete and we have to pick a vertex from each of them. Thus Lemma 3.2 applied to guarantees the existence of two members with a corresponding separator of independence number at most . We are left with finding such a pair and the corresponding separator of independence number at most in polynomial time.
For every unordered pair of distinct , we proceed as follows. Define and construct a -system in consisting of:
the sets of internal vertices of all induced –-paths of length at most ; and
all sets such that is an induced path for some .
According to the definition above, we distinguish the members of of the first and second type, respectively. Note that every –-path has at least one internal vertex, as and are anticomplete. Consequently, every member of is nonempty and has size at most .
Claim 3.4.1. Every hitting set for is an –-separator.
Proof of Claim 3.4.1: Suppose otherwise and let be a shortest –-path in . In particular, is induced. If has length at most , then the set of its internal vertices is a member of of the first type, contradicting the choice of . Otherwise, consecutive vertices of , starting at the neighbor of the endpoint in , form a member of of the second type, again contradicting the choice of . ⌟
Claim 3.4.2. For every , the system contains at most pairwise anticomplete members of the second type.
Proof of Claim 3.4.2: Suppose otherwise. By the pigeonhole principle, three witnessing paths would have a common endpoint in , since . As, except for the common endpoint, the paths are pairwise anticomplete, they would form an induced in , a contradiction. ⌟
For the pair , there are also at most pairwise anticomplete members of the first type: the separator hits each of them, and choosing one vertex from each intersection gives an independent set in the separator. Consequently, has no pairwise anticomplete members.
Apply Lemma 3.3 to each in with parameters . Since the second outcome is impossible for the pair , at least one call returns a hitting set for some with . As Lemma 3.3 was invoked in , we have that . Thus, by Claim 3.4.1, is an –-separator, and we can return as the second outcome of Lemma 3.4.
Note that there are pairs and each family can be constructed by exhaustively enumerating paths of length at most . As all parameters are fixed, the running time is polynomial.
Obtaining a balanced extended strip decomposition
Bourneuf, Masaříková, Nadara, and Pilipczuk [5] proved that, given an -free graph and a mass function, one can remove a constant number of closed neighborhoods to obtain a rigid balanced extended strip decomposition of the remaining graph.
Theorem 3.5 ([5], Theorem 3). Given an -free graph and a mass function , one can in polynomial time find with and a rigid extended strip decomposition of that is balanced for .
In this subsection we aim to obtain an analogous statement, but instead of removing few closed neighborhoods, we will remove a set of vertices of bounded independence number. We remark that an existential statement of Lemma 3.6 can be quite easily obtained by combining Theorem 3.5 with a result of Hajebi and Spirkl [18 Lemma 7.2]. However, we need an algorithmic variant.
Lemma 3.6. For fixed , there is a computable constant and a polynomial-time algorithm which, given an -vertex -free graph with mass function , finds with and an extended strip decomposition of that is balanced for and whose host has vertices and edges.
Proof. Define the following constants depending only on :
Throughout the execution of the algorithm, we will maintain a -system ; the algorithm starts with . With each we store a set with and a rigid extended strip decomposition of that is balanced for . By Proposition 2.1(3), every stored host has at most vertices and edges.
Iteratively, we apply Lemma 3.4 to the current system .
Suppose first that the application returns the second outcome, i.e., two anticomplete members and an –-separator with . Define , so . No component of meets both and : such a component, together with an endpoint in each , would give an –-path in . Let be the union of the components avoiding , and set . Then are anticomplete and
Restrict to and take the disjoint union of the two decompositions. By Proposition 2.1(1) and (2), this is a decomposition of , and each new particle is contained in a stored particle. Hence the result is balanced for . Restriction leaves the hosts unchanged, so their union has at most vertices and at most edges. Return and this decomposition, and terminate. We remark that the restrictions may destroy rigidity, but the outcome of this step is never stored in .
So, suppose that the application of Lemma 3.4 returns the first outcome, i.e., a hitting set for with . Apply Theorem 3.5 to with the restriction of . We obtain a set with and a rigid extended strip decomposition of whose particles have mass at most . If , return and , and terminate. This satisfies the required independence-number bound since , and the host has at most vertices and edges by rigidity.
Otherwise, add to , set and , and proceed to the next iteration. Note that was not already a member of : it is disjoint from , whereas every previous member meets . Thus every nonterminating iteration adds a new member to , and there are at most possible members. Each iteration takes polynomial time, using Lemma 3.4 and Theorem 3.5 and, in the terminating separator case, restriction and disjoint union. Hence the entire algorithm runs in polynomial time.
Small interfaces and component boundaries
Fix and let be an extended strip decomposition of a -free graph . Call a vertex set small if its independence number is at most , and large otherwise. At most one interface at a given host vertex is large: two such interfaces would contain independent -vertex sets complete to one another, inducing a . For every , define
Thus is the union of all small interfaces. As all interfaces at are complete to each other, we have . However, the independence number of might be arbitrarily large. For fixed , sets and can be found in polynomial time by exhaustively enumerating -vertex sets in each interface.
Lemma 3.7. Let be an integer, let be an extended strip decomposition of a -free graph . Let for each and be defined as in (1). Then the following hold.
(1) for every particle of .
(2) Every component of is contained in a particle of and satisfies .
Proof. The set lies entirely in the union of edge atoms, and, for every edge , is the union of the small interfaces of . Hence . Since every particle meets at most one edge atom, this proves item (1).
To prove item (2), let be a component of ; in particular, .
Claim 3.7.1. The component is contained in a particle of .
Proof of Claim 3.7.1: Let be the extended strip decomposition of obtained by restricting to , as in Proposition 2.1(1). Every small interface becomes empty, so at each host vertex at most one interface of is nonempty. By the definition of an extended strip decomposition, every edge between two distinct edge atoms joins two interfaces at a common host vertex. Hence distinct edge atoms of are anticomplete. Similarly, all neighbors of a vertex atom lie in the unique nonempty interface at , if it exists, so has neighbors in at most one edge atom. A triangle atom has neighbors only in the edge atoms , , and . Moreover, it has a neighbor in only if both and are nonempty, and analogously for and . As any two of the edges , , and of share a vertex, and at each host vertex at most one interface of is nonempty, at most one of these three edges has both of its interfaces in nonempty. Hence also has neighbors in at most one edge atom. Distinct vertex and triangle atoms are anticomplete. Consequently, as is connected, it meets at most one edge atom of . If meets , then, as is connected and meets no other edge atom, every vertex or triangle atom meeting has a neighbor in . Thus every such atom is , , or for some , and hence . Otherwise, meets no edge atom, so it is contained in a single vertex or triangle atom, as distinct vertex and triangle atoms are anticomplete. In both cases, is contained in a particle of .
Thus, it remains to show that . Let us first consider the case when meets an edge atom for some .
Claim 3.7.2. If meets for some , then . In particular, .
Proof of Claim 3.7.2: Every particle meeting is one of , , , and , and all of them are contained in . Hence by Claim 3.7.1. Neighbors of in lie in , and thus in . Since , every neighbor of lies in an edge atom. By the definition of an extended strip decomposition, every neighbor of outside thus lies in an interface with or in an interface with . By symmetry, let be a neighbor of of the first kind; we show that . The only vertices of that can be adjacent to lie in , in , or in if , so meets one of these sets. In fact, meets . Indeed, all neighbors of and of in lie in , and if meets one of these two atoms, then it also contains a neighbor of this atom, as is connected and meets . As , the interface is not contained in , so it is large. Since at most one interface at is large, is small, and hence . Now, the bound on follows from the bound on and .
Now, consider the case when meets no edge atom, i.e., it is contained in a single vertex or triangle atom. Since , the definition of an extended strip decomposition implies the following:
if for some , then is contained in the union of the sets over all ;
if for some , then is contained in the union of the sets , , and .
In both cases, any two of these sets are contained in two distinct interfaces at a common host vertex, and hence they are complete to each other. Thus every independent subset of is contained in one of these sets. Moreover, each of these sets is contained in for some full edge particle , so its independence number is at most by item (1). Therefore , which completes the proof of item (2). ∎
Excluding a single long claw
In this section we prove Theorem 1.1 for , using Lemmas 3.6 and 3.7. We follow the recursive scheme of Abrishami, Chudnovsky, Dibek, Pilipczuk, and Rzążewski [1 Section 3], keeping terminal sets of bounded independence number.
Fix integers , ; we treat them as fixed constants. Fix an ambient -free weighted graph , which will remain unchanged throughout the recursion.
Auxiliary problem
In the recursion, we solve a more general problem than the original one. An instance is a pair of disjoint subsets of , and its graph is with weights . The vertices of are called terminals and the set is called the interior of the instance.
The goal for an instance is to compute the auxiliary table entries for all independent sets . Each entry stores the largest weight that the interior can contribute when precisely the terminals in are selected:
In particular, .
For a set and an independent set , define . Then, for every independent ,
Indeed, after fixing the selected vertices of , the remaining set is an independent set in .
Child instances
Fix an instance with graph . We define child instances whose tables determine . Let and let be an extended strip decomposition of . Let be defined as in (1), and define . For every particle , let consist of the vertex sets of the components of . Define , where the union ranges over all particles of . For each , define its boundary and the child instance , whose interior is . Note that even when , its boundary need not be contained in . We compute each child table once, even if occurs for several particles.
Clearly, one can construct and all child instances in time polynomial in .
Lemma 4.1. Every vertex of belongs to at most four members of . Consequently, we have
Proof. Every particle is contained in and , so every member of is a subset of . Hence the second statement follows from the first, and it suffices to prove the first statement for a fixed vertex . For every particle containing , let be the vertex set of the component of containing . Then is the unique member of containing , so the members of containing are exactly the sets , where ranges over the particles containing .
If lies in an edge atom , then every particle containing is one of , , , and . If lies in a triangle atom , then every particle containing is one of , , , , and . In both cases, there are at most four sets .
It remains to consider the case that lies in a vertex atom for some . By the definition of particles, the particles containing are exactly the following:
the vertex particle , and
the half-edge particle and the full edge particle for each .
We show that at most three of the sets are distinct.
By the definition of an extended strip decomposition, every vertex of lies in an interface for some . Let be such that is small, and let . Since is disjoint from all edge atoms other than , we have by (1). Thus is anticomplete to , and since is connected and contains , we obtain . As , this yields .
Finally, recall that at most one interface at is large. Hence every set equals , except possibly and for the unique with large, if such a exists. Thus at most three of the sets are distinct.
Lemma 4.2. Given the child tables, we can compute in time polynomial in per independent subset of .
Proof. Fix an independent set and let be as in (2). For every particle , we have
Indeed, after fixing , the remaining choices lie in the pairwise anticomplete components . As , the choices in each must be compatible precisely with , as encoded by the corresponding table entry. By Lemma 3.7[1], there are choices of . Restrict to using Proposition 2.1[1], and apply Theorem 2.2 with the values in (3) to compute . Equation (2) gives the parent table. This uses only the supplied child tables.
:::
Proof of thm:main for a single long claw
Theorem 4.3 (Theorem 1.1 for a single long claw). For every fixed , there is a polynomial-time algorithm which, given an -free graph and a weight function , returns a maximum-weight independent set in .
Proof. Let . If or , the result is obvious. Thus suppose and , and define ; this constant depends only on .
Throughout the recursion, we compute the table for an instance while maintaining . The initial call uses and . At each call, define . If , compute each table entry directly. Otherwise proceed as follows.
Enumerate all independent subsets of of size at most . Choose one of maximum cardinality, say , and write .
If , let be the indicator mass function of . Otherwise, let be the indicator mass function of . Apply Lemma 3.6 to with this mass function, obtaining with and a balanced extended strip decomposition of with a host of linear size. Define its small-interface set as in (1).
Construct the distinct children as in § 4.2 and recursively compute , once per child.
Compute the parent table using Lemma 4.2.
We verify that the terminal bound is preserved and that the recursion terminates. For a child , let be the component of containing . Since , Lemma 3.7[2] gives
If , the decomposition is balanced for the indicator mass function of the interior. Since is contained in a particle, we obtain
Suppose instead that . The decomposition is balanced for the indicator mass function of , so . Replacing by any independent set in preserves independence, as is anticomplete to . Since is a maximum independent set of , this gives
Thus the terminal bound is preserved, and any call that does not halve the interior has children with terminal independence number at most . Every two recursion levels therefore halve the interior, so the recursion terminates. Each child graph is induced in and hence remains -free. Correctness now follows by induction using Lemma 4.2. At the root, .
The recursion has depth , and Lemma 4.1 bounds the sum of the interior sizes at depth by . Since all child interiors are nonempty, the recursion tree has polynomially many nodes. At each node, Lemma 3.6 takes polynomial time and produces a host of linear size. The bounds and give polynomially many table entries and assignments in Lemma 4.2. Hence each node takes polynomial time apart from its recursive calls, and the total running time is polynomial. Finally, a maximum-weight independent set can be recovered by standard bookkeeping.
Excluding a disjoint union of long claws
In this section we prove Theorem 1.1. On a high level, another application of Lemma 3.3 reduces the problem to the case of a single long claw, which can then be solved using Theorem 4.3.
Theorem 1.1. For every fixed and , there is a polynomial-time algorithm which, given an -free graph and a weight function , returns a maximum-weight independent set in .
Proof. Let be the number of components of and let . Then is an induced subgraph of , and hence every -free graph is also -free.
Define , and let consist of the vertex sets of all induced copies of in . This is a -system that can be constructed in polynomial time by enumerating all -vertex subsets of . Apply Lemma 3.3 to with parameters . The second outcome gives pairwise anticomplete induced copies of , inducing in . Thus we obtain a hitting set with . Since meets every induced copy of , the graph is -free.
Clearly,
The bound on lets us enumerate all independent subsets in polynomial time. For each , the residual graph is induced in and hence is -free. Solve MWIS in this graph using Theorem 4.3, and add to the resulting independent set. Returning the heaviest set obtained in this way gives a maximum-weight independent set in . Since are fixed, the construction of , the application of Lemma 3.3, and all residual computations take polynomial time.
Conclusion
The main challenge remains to solve MWIS in polynomial time in graphs excluding an arbitrary fixed subdivided claw, with no further assumptions. We believe that extended strip decompositions are the right tool, but that further progress will require controlling the structure of particles, rather than just their size. The goal would be to find, in polynomial time, a decomposition whose particles admit efficient algorithms for MWIS. The structure theorem of Chudnovsky and Seymour for claw-free graphs [12] provides a model for such an approach.
Abrishami et al. [2] considered -free graphs, for , excluding a fixed biclique as a subgraph. By Ramsey’s theorem, this restriction is equivalent, up to changing the parameters, to excluding both a fixed clique and a fixed biclique as induced subgraphs. Our result strengthens this result by removing the clique exclusion. The complementary direction is to retain only the clique exclusion. This direction was proposed by Abrishami et al. [2 Conjecture 10], and we restate it here.
Problem 6.1. For every fixed and integer , can MWIS be solved in polynomial time in -free graphs?
Even the special case where is a path remains open in general.
Problem 6.2. For every fixed pair of integers , can MWIS be solved in polynomial time in -free graphs?
This question (in the unweighted setting) was explicitly asked by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [10], and remains wide open. Recall from the introduction that recently the case was settled in the affirmative [9].
Acknowledgement. ChatGPT was used to simplify some constructions and to identify or correct omissions and minor mistakes and Claude was used to polish the write-up. The authors take full responsibility for the content of the paper.
References
- [1]T. Abrishami, M. Chudnovsky, C. Dibek, M. Pilipczuk, and P. Rzążewski. Max weight independent set in sparse graphs with no long claws. ACM Trans. Algorithms, Sept. 2026. Just Accepted.arxiv.org/abs/2309.16995
- [2]T. Abrishami, M. Chudnovsky, C. Dibek, M. Pilipczuk, and P. Rzążewski. Max weight independent set in sparse graphs with no long claws. arXiv:2309.16995v3, 2024.arxiv.org/abs/2309.16995
- [3]T. Abrishami, M. Chudnovsky, C. Dibek, and P. Rzążewski. Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws. In J. S. Naor and N. Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, January 9-12, 2022, pages 1448–1470. SIAM, 2022.arxiv.org/abs/2107.05434
- [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.
- [5]R. Bourneuf, J. Masaríková, W. Nadara, and M. Pilipczuk. Graphs with no long claws: An improved bound for the analog of the Gyárfás’ path argument. In P. Gawrychowski, F. Mazowiecki, and M. Skrzypczak, editors, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland, August 25-29, 2025, volume 345 of LIPIcs, pages 28:1–28:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2501.13907
- [6]A. Brandstädt, V. V. Lozin, and R. Mosca. Independent sets of maximum weight beyond claw-free graphs and related problems. Theoretical Computer Science, 1032:115103, 2025.DOI
- [7]A. Brandstädt and R. Mosca. Maximum weight independent sets for (P₇, triangle)-free graphs in polynomial time. Discret. Appl. Math., 236:57–65, 2018.arxiv.org/abs/1511.08066
- [8]A. Brandstädt and R. Mosca. Maximum weight independent set for ℓclaw-free graphs in polynomial time. Discrete Applied Mathematics, 237:57–64, mar 2018.
- [9]M. Chudnovsky, J. Czyżewska, K. Kluk, M. Pilipczuk, and P. Rzążewski. Sparse induced subgraphs in P₇-free graphs of bounded clique number. In 36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.arxiv.org/abs/2412.14836
- [10]M. Chudnovsky, J. King, M. Pilipczuk, P. Rzążewski, and S. Spirkl. Finding large H-colorable subgraphs in hereditary graph classes. SIAM Journal on Discrete Mathematics, 35(4):2357–2386, 2021.arxiv.org/abs/2004.09425
- [11]M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, and S. Thomassé. Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs. SIAM Journal on Computing, 53(1):47–86, 2024.
- [12]M. Chudnovsky and P. D. Seymour. Claw-free graphs. V. Global structure. J. Comb. Theory, Ser. B, 98(6):1373–1410, 2008.DOI
- [13]Y. Faenza, G. Oriolo, and G. Stauffer. An algorithmic decomposition of claw-free graphs leading to an O(n³)-algorithm for the weighted stable set problem. In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pages 630–646, USA, 2011. Society for Industrial and Applied Mathematics.
- [14]P. Gartland and D. Lokshtanov. Independent set on Pₖ-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
- [15]P. Gartland, D. Lokshtanov, T. Masarík, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Maximum 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 Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24–28, 2024, pages 683–691. ACM, 2024.DOI
- [16]M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169–197, 1981.DOI
- [17]A. Grzesik, T. Klimašová, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithm for maximum weight independent set on P₆-free graphs. ACM Trans. Algorithms, 18(1):4:1–4:57, 2022.
- [18]S. Hajebi and S. Spirkl. Tree-alpha and excluding finitely many graphs. CoRR, abs/2605.01223, 2026.arxiv.org/abs/2605.01223
- [19]R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer US, 1972.
- [20]T. Kővari, V. T. Sós, and P. Turán. On a problem of K. Zarankiewicz. Colloq. Math., 3:50–57, 1954.DOI
- [21]D. Kühn and D. Osthus. Induced subdivisions in Kₛ,ₛ-free graphs of large average degree. Combinatorica, 24:287–304, 2004.
- [22]D. Lokshtanov, M. Vatshelle, and Y. Villanger. Independent set in P₅-free graphs in polynomial time. 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.
- [23]V. V. Lozin and M. Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms, 6(4):595–604, 2008.
- [24]F. Maffray and L. Pastor. Maximum weight stable set in (P₇, bull)-free graphs. CoRR, abs/1611.09663, 2016.
- [25]K. Majewski, T. Masarík, J. Masaríková, K. Okrasa, M. Pilipczuk, P. Rzążewski, and M. Sokołowski. Max weight independent set in graphs with no long claws: An analog of the Gyárfás’ path argument. ACM Transactions on Computation Theory, 16(2):8:1–8:18, Mar. 2024.
- [26]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
- [27]R. Mosca. Stable sets of maximum weight in (P₇, banner)-free graphs. Discrete Mathematics, 308(1):20–33, 2008.DOI
- [28]M. Pilipczuk, M. Pilipczuk, and P. Rzążewski. Quasi-polynomial-time algorithm for independent set in P_t-free graphs via shrinking the space of induced paths. In H. V. Le and V. King, editors, 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11–12, 2021, pages 204–209. SIAM, 2021.arxiv.org/abs/2009.13494
- [29]N. Sbihi. Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile. Discrete Mathematics, 29(1):53–76, 1980.DOI
- [30]G. Valiente. A new simple algorithm for the maximum-weight independent set problem on circle graphs. In Algorithms and Computation, ISAAC 2003, volume 2906 of Lecture Notes in Computer Science, pages 129–137. Springer, 2003.DOI
