betaFeedback

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 FF and GG, the graph GG is FF-free if GG contains no induced subgraph isomorphic to FF. More generally, GG is (F1,…,Fk)(F_1,\ldots,F_k)-free if it is FiF_i-free for every ii. For t≥1t \ge1, let PtP_t denote the path on tt vertices, i.e., of length t−1t-1. For a,b,c≥1a,b,c \ge1, the subdivided claw Sa,b,cS_{a,b,c} is obtained from three paths of lengths a,b,ca,b,c by identifying one endpoint of each path into a single vertex. In particular, S1,1,1=K1,3S_{1,1,1}=K_{1,3} is the three-leaf star, also known as the claw. Let F\mathcal{F} be the family of all graphs GG such that each component of GG is a subcubic tree with at most three leaves, or equivalently, a path or a subdivided claw.

Alekseev [4] showed that, for every fixed F∉FF \notin\mathcal{F}, 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 FF-free graphs. For F∈FF \in\mathcal{F}, polynomial-time algorithms are known only in special cases. Notable examples include P5P_5-free graphs, by Lokshtanov, Vatshelle, and Villanger [22]; P6P_6-free graphs, by Grzesik, Klimošová, Pilipczuk, and Pilipczuk [17]; and fork-free graphs, by Lozin and Milanič [23], where the fork is S2,1,1S_{2,1,1}. There are also nontrivial tractable cases with disconnected forbidden graphs [6, 8].

Interestingly, for every F∈FF \in\mathcal{F}, MWIS in FF-free graphs can be solved in quasipolynomial time. This was first established by Gartland and Lokshtanov [14] (see also [28]) for the case that FF is a path, and then extended to general F∈FF \in\mathcal{F} 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 FF-free graphs under additional restrictions. For example, polynomial-time algorithms for MWIS are known for graphs that exclude P7P_7 and some small graphs [7, 24, 27]. Recently, MWIS was shown to be polynomial-time-solvable in P7P_7-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 F∈FF \in\mathcal{F} and integer Δ\Delta, Abrishami, Chudnovsky, Dibek, and Rzążewski [3] gave a polynomial-time algorithm for MWIS in FF-free graphs of maximum degree at most Δ\Delta. 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 s≥1s \ge1 and F∈FF \in\mathcal{F}, there is a polynomial-time algorithm which, given an (F,Ks,s)(F,K_{s,s})-free graph GG and a weight function w:V(G)→R≥0w: V(G) \to\mathbb{R}_{\ge0}, returns a maximum-weight independent set in (G,w)(G,w).

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 FF-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 FF 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 GG be a graph and let w:V(G)→R≥0\mathrm{w}: V(G) \to\mathbb{R}_{\ge0} be a weight function on the vertices of GG. A vertex-weighted graph is a pair (G,w)(G,\mathrm{w}). We also use w\mathrm{w} for its restriction to any induced subgraph of GG. For a set X⊆V(G)X \subseteq V(G), we define w(X):=∑v∈Xw(v)\mathrm{w}(X) := \sum_{v\in X} \mathrm{w}(v), and we write w(G):=w(V(G))\mathrm{w}(G) := \mathrm{w}(V(G)). 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 μ\mu. Usually, the mass will be defined for a subset U⊆V(G)U \subseteq V(G) as μ(v)=1\mu(v) = 1 if v∈Uv \in U and μ(v)=0\mu(v) = 0 otherwise. We will call such a function indicator mass function of UU.

Graph theory. For two graphs G1G_1 and G2G_2, we denote by G1+G2G_1 + G_2 the disjoint union of G1G_1 and G2G_2. For X⊆V(G)X \subseteq V(G), let NG(X)N_G(X) be the set of neighbors of XX, i.e., vertices outside XX with a neighbor in XX, and write NG[X]=X∪NG(X)N_G[X] = X \cup N_G(X). Two sets are anticomplete if they are disjoint and no edge joins them. For a graph GG, by α(G)\alpha(G) we denote the independence number of GG, i.e., the size of a maximum independent set in GG. For a vertex-weighted graph (G,w)(G,\mathrm{w}), by α(G,w)\alpha(G,\mathrm{w}) we denote the maximum weight of an independent set in GG with respect to w\mathrm{w}. If GG is clear from the context, for X⊆V(G)X \subseteq V(G) we will write α(X)\alpha(X) and α(X,w)\alpha(X,\mathrm{w}) instead of α(G[X])\alpha(G[X]) and α(G[X],w)\alpha(G[X],\mathrm{w}), respectively.

Paths in graphs. Let GG be a graph and let AA, BB be disjoint subsets of V(G)V(G). By AA–BB-path we mean a path in GG with one endpoint in AA, the other endpoint in BB, and all internal vertices in V(G)∖(A∪B)V(G) \setminus(A \cup B). An AA–BB-separator is a set Y⊆V(G)∖(A∪B)Y \subseteq V(G) \setminus(A \cup B) that intersects all AA–BB-paths in GG.

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 HH, by T(H)T(H) we denote the set of triangles in HH. We write xyzxyz for a triangle {x,y,z}\{x,y,z\}. An extended strip decomposition of a graph GG is a pair (H,η)(H,\eta) that consists of:

  • a simple graph HH called the host,

  • a vertex atom η(x)⊆V(G)\eta(x) \subseteq V(G) for every x∈V(H)x \in V(H),

  • an edge atom η(xy)⊆V(G)\eta(xy) \subseteq V(G) for every xy∈E(H)xy \in E(H), and its subsets η(xy,x),η(xy,y)⊆η(xy)\eta(xy,x),\eta(xy,y) \subseteq\eta(xy) called interfaces, and

  • a triangle atom η(xyz)⊆V(G)\eta(xyz) \subseteq V(G) for every xyz∈T(H)xyz \in T(H),

which have the following properties (empty sets are allowed):

  1. The family {η(o)∣o∈V(H)∪E(H)∪T(H)}\{\eta(o) \mid o \in V(H) \cup E(H) \cup T(H)\} is a partition of V(G)V(G).

  1. For every x∈V(H)x \in V(H) and every distinct y,z∈NH(x)y,z \in N_H(x), the set η(xy,x)\eta(xy,x) is complete to η(xz,x)\eta(xz,x) (i.e., all possible edges between these two sets exist).

  1. Every uv∈E(G)uv \in E(G) is contained in one of the atoms η(o)\eta(o) for o∈V(H)∪E(H)∪T(H)o \in V(H) \cup E(H) \cup T(H), or is as follows:

  • u∈η(xy,x),v∈η(xz,x)u \in\eta(xy,x), v \in\eta(xz,x) for some x∈V(H)x \in V(H) and y,z∈NH(x)y,z \in N_H(x), or

  • u∈η(xy,x),v∈η(x)u \in\eta(xy,x), v \in\eta(x) for some xy∈E(H)xy \in E(H), or

  • u∈η(xyz)u \in\eta(xyz) and v∈η(xy,x)∩η(xy,y)v \in\eta(xy,x) \cap\eta(xy,y) for some xyz∈T(H)xyz \in T(H).

A schematic picture of an extended strip decomposition of a graph is shown in Figure 1.

Figure 1. A graph HH (top) and a schematic view of an extended strip decomposition (H,η)(H,\eta) of a graph GG. Green areas depict the sets η(xy,y)\eta(xy,y). 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 (H,η)(H,\eta) is rigid if for every xy∈E(H)xy \in E(H), the sets η(xy,x)\eta(xy,x) and η(xy,y)\eta(xy,y) are nonempty, and for every isolated x∈V(H)x \in V(H), the vertex atom η(x)\eta(x) is nonempty.

For an extended strip decomposition (H,η)(H,\eta) of a graph GG, we identify five types of particles.

vertex particle: Ax:=η(x)A_x := \eta(x) for each x∈V(H)x \in V(H),

edge interior particle: Axy∘:=η(xy)∖(η(xy,x)∪η(xy,y))A_{xy}^{\circ} := \eta(xy) \setminus\left(\eta(xy,x) \cup\eta(xy,y)\right) for each xy∈E(H)xy \in E(H),

half-edge particle: Axyx:=η(x)∪η(xy)∖η(xy,y)A_{xy}^{x} := \eta(x) \cup\eta(xy) \setminus\eta(xy,y) for each xy∈E(H)xy \in E(H),

full edge particle: Axyxy:=η(x)∪η(y)∪η(xy)∪⋃z∣xyz∈T(H)η(xyz)A_{xy}^{xy} := \eta(x) \cup\eta(y) \cup\eta(xy) \cup\bigcup_{z\mid xyz\in T(H)} \eta(xyz) for each xy∈E(H)xy \in E(H),

triangle particle: Axyz:=η(xyz)A_{xyz} := \eta(xyz) for each xyz∈T(H)xyz \in T(H).

Given a mass function μ\mu on V(G)V(G), a decomposition of an induced subgraph of GG is *balanced for μ\mu if every particle AA satisfies μ(A)≤μ(G)/2\mu(A) \leq\mu(G)/2.

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.

  1. Let GG be a graph, let (H,η)(H,\eta) be an extended strip decomposition of GG, and let X⊆V(G)X \subseteq V(G). By restricting η\eta to XX, we obtain an extended strip decomposition of G[X]G[X], with every particle replaced by its intersection with XX.

  1. Let G1,G2G_1,G_2 be two graphs on disjoint vertex sets, let (H1,η1)(H_1,\eta_1) and (H2,η2)(H_2,\eta_2) be extended strip decompositions of G1G_1 and G2G_2, respectively. Then, by taking the disjoint union of H1H_1 and H2H_2 and the union of η1\eta_1 and η2\eta_2, we obtain an extended strip decomposition of G1+G2G_1+G_2.

  1. If (H,η)(H,\eta) is a rigid extended strip decomposition of GG, then ∣V(H)∣≤2∣V(G)∣|V(H)| \leq2|V(G)| and ∣E(H)∣≤∣V(G)∣|E(H)| \leq|V(G)|.

The main algorithmic application of extended strip decompositions is that, given an extended strip decomposition (H,η)(H,\eta) of (G,w)(G,w), one can reduce computing α(G,w)\alpha(G,w) to solving MWIS in particles of (H,η)(H,\eta).

Theorem 2.2 (Chudnovsky, Pilipczuk, Pilipczuk, and Thomassé [11 Section 3.3]). Given a weighted graph (G,w)(G,w), an extended strip decomposition (H,η)(H,\eta) of GG, and the value α(A,w)\alpha(A,w) for every particle AA, one can compute α(G,w)\alpha(G,w) in time polynomial in ∣V(G)∣+∣V(H)∣|V(G)|+|V(H)|.

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 GG and an integer bb, a bb-system in GG is a family of nonempty vertex sets of GG, each of size at most bb; 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, bb-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 b,s,q≥1b,s,q \geq1, there is a computable constant c3.1=c3.1(b,s,q)∈Nc_{3.1}=c_{3.1}(b,s,q) \in\mathbb{N} such that, for every Ks,sK_{s,s}-free graph GG and every bb-system SS in GG, one of the following holds:

  1. there is a hitting set X⊆V(G)X \subseteq V(G) for SS with α(X)≤c3.1\alpha(X) \leq c_{3.1}; or

  1. there are qq pairwise anticomplete members of SS.

Lemma 3.2 (Hajebi and Spirkl [18 Theorem 3.1]). For every b,s,t≥1b,s,t \ge1, there are computable constants c3.2=c3.2(b,s,t)∈Nc_{3.2}=c_{3.2}(b,s,t)\in\mathbb{N} and d3.2=d3.2(b,s,t)∈Nd_{3.2}=d_{3.2}(b,s,t)\in\mathbb{N} such that, for every (St,t,t,Ks,s)(S_{t,t,t},K_{s,s})-free graph GG and every bb-system S\mathcal{S} in GG, one of the following holds:

  1. there is a hitting set X⊆V(G)X\subseteq V(G) for S\mathcal{S} with α(X)≤c3.2\alpha(X)\le c_{3.2}; or

  1. there are anticomplete S1,S2∈SS_1,S_2\in\mathcal{S} and an S1S_1–S2S_2-separator YY with α(Y)≤d3.2\alpha(Y)\le d_{3.2}.

Lemma 3.3 (Algorithmic Lemma 3.1). For fixed b,s,q≥1b,s,q\ge1, there is a computable constant c3.3=c3.3(b,s,q)c_{3.3}=c_{3.3}(b,s,q) and a polynomial-time algorithm which, given a bb-system S\mathcal{S} in a Ks,sK_{s,s}-free graph GG, returns either:

  1. a hitting set XX for S\mathcal{S} with α(X)≤c3.3\alpha(X)\le c_{3.3}; or

  1. qq pairwise anticomplete members of S\mathcal{S}.

Proof. Enumerate all qq-tuples of members of S\mathcal{S} and return an anticomplete tuple if it exists. This can be done in polynomial time, as both bb and qq are fixed.

Otherwise, Lemma 3.1 guarantees a hitting set of independence number at most c3.1=c3.1(b,s,q)c_{3.1}=c_{3.1}(b,s,q). Without loss of generality we may assume that this hitting set is contained in ⋃S\bigcup\mathcal{S}. Solve the rational feasibility program

0≤xv≤1for every v∈⋃S,∑v∈Sxv≥1for every S∈S,∑v∈Ixv≤c3.1for every independent set I⊆⋃S with ∣I∣=b⋅c3.1+1.\begin{aligned} 0 &\le x_v \le1 &&\text{for every }v\in\bigcup\mathcal{S},\\ \sum_{v\in S}x_v &\ge1 &&\text{for every }S\in\mathcal{S},\\ \sum_{v\in I}x_v &\le c_{3.1} &&\text{for every independent set }I\subseteq\bigcup\mathcal{S}\text{ with }|I|=b\cdot c_{3.1}+1. \end{aligned}

This linear program has a solution: indeed, the indicator vector of the guaranteed hitting set satisfies every constraint. Take X={v∣xv≥1/b}X=\{v\mid x_v\ge1/b\}.

By the second family of constraints, for every S∈SS\in\mathcal{S}, we have ∑v∈Sxv≥1\sum_{v\in S}x_v\ge1, and hence X∩S≠∅X\cap S\ne\varnothing. On the other hand, α(X)≤b⋅c3.1\alpha(X)\le b\cdot c_{3.1}, as otherwise we would have an independent set I⊆X⊆⋃SI\subseteq X\subseteq\bigcup\mathcal{S} of size b⋅c3.1+1b\cdot c_{3.1}+1, and then ∑v∈Ixv≥∣I∣/b>c3.1\sum_{v\in I}x_v\ge|I|/b>c_{3.1}, violating the last constraint of the program. Thus we can set c3.3(b,s,q)=b⋅c3.1(b,s,q)c_{3.3}(b,s,q)=b\cdot c_{3.1}(b,s,q).

Note that the number of constraints is polynomial in ∣V(G)∣|V(G)|, as bb and c3.1c_{3.1} are constants. As linear programs can be solved in polynomial time, the proof is complete. □

Lemma 3.4 (Algorithmic Lemma 3.2). For every b,s,t≥1b,s,t\ge1, there are constants c3.4=c3.4(b,s,t)∈Nc_{3.4}=c_{3.4}(b,s,t)\in\mathbb{N} and d3.4=d3.4(b,s,t)∈Nd_{3.4}=d_{3.4}(b,s,t)\in\mathbb{N} and a polynomial-time algorithm that, given an (St,t,t,Ks,s)(S_{t,t,t},K_{s,s})-free graph GG and a bb-system S\mathcal{S} in GG, returns either:

  1. a hitting set X⊆V(G)X\subseteq V(G) for S\mathcal{S} with α(X)≤c3.4\alpha(X)\le c_{3.4}; or

  1. two anticomplete members S1,S2∈SS_1,S_2\in\mathcal{S} and an S1S_1–S2S_2-separator YY with α(Y)≤d3.4\alpha(Y)\le d_{3.4}.

Proof. Define the following constants depending only on b,s,tb,s,t:

q=c3.2(b,s,t)+1,q=c_{3.2}(b,s,t)+1,
c3.4=c3.3(b,s,q),c_{3.4}=c_{3.3}(b,s,q),
d3.4=c3.3(t,s,d3.2+2b+1).d_{3.4}=c_{3.3}(t,s,d_{3.2}+2b+1).

Apply Lemma 3.3 to S\mathcal{S} with parameters b,s,qb,s,q. If the call returns the first outcome, i.e., a hitting set with independence number at most c3.4c_{3.4}, we return it as the first outcome.

Thus, suppose that the application of Lemma 3.3 returns a subfamily A⊆S\mathcal{A}\subseteq\mathcal{S} consisting of qq pairwise anticomplete members of S\mathcal{S}. Every hitting set for A\mathcal{A} has independence number at least qq, as the qq sets in A\mathcal{A} are pairwise anticomplete and we have to pick a vertex from each of them. Thus Lemma 3.2 applied to A\mathcal{A} guarantees the existence of two members S^1,S^2\widehat{S}_1,\widehat{S}_2 with a corresponding separator Y^\widehat{Y} of independence number at most d3.2d_{3.2}. We are left with finding such a pair and the corresponding separator of independence number at most d3.4d_{3.4} in polynomial time.

For every unordered pair of distinct S1,S2∈AS_1,S_2\in\mathcal{A}, we proceed as follows. Define W=V(G)∖(S1∪S2)W=V(G)\setminus(S_1\cup S_2) and construct a tt-system HS1,S2\mathcal{H}_{S_1,S_2} in G[W]G[W] consisting of:

  1. the sets of internal vertices of all induced S1S_1–S2S_2-paths of length at most tt; and

  1. all sets {v1,…,vt}⊆W\{v_1,\ldots,v_t\} \subseteq W such that v0,v1,…,vtv_0,v_1,\ldots,v_t is an induced path for some v0∈S1v_0 \in S_1.

According to the definition above, we distinguish the members of HS1,S2\mathcal{H}_{S_1,S_2} of the first and second type, respectively. Note that every S1S_1–S2S_2-path has at least one internal vertex, as S1S_1 and S2S_2 are anticomplete. Consequently, every member of HS1,S2\mathcal{H}_{S_1,S_2} is nonempty and has size at most tt.

Claim 3.4.1. Every hitting set Y⊆WY \subseteq W for HS1,S2\mathcal{H}_{S_1,S_2} is an S1S_1–S2S_2-separator.

Proof of Claim 3.4.1: Suppose otherwise and let PP be a shortest S1S_1–S2S_2-path in G−YG-Y. In particular, PP is induced. If PP has length at most tt, then the set of its internal vertices is a member of HS1,S2\mathcal{H}_{S_1,S_2} of the first type, contradicting the choice of YY. Otherwise, tt consecutive vertices of PP, starting at the neighbor of the endpoint in S1S_1, form a member of HS1,S2\mathcal{H}_{S_1,S_2} of the second type, again contradicting the choice of YY. ⌟

Claim 3.4.2. For every S1,S2S_1,S_2, the system HS1,S2\mathcal{H}_{S_1,S_2} contains at most 2b2b 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 S1S_1, since ∣S1∣≤b|S_1| \leq b. As, except for the common endpoint, the paths are pairwise anticomplete, they would form an induced St,t,tS_{t,t,t} in GG, a contradiction. ⌟

For the pair S^1,S^2\widehat{S}_1,\widehat{S}_2, there are also at most d3.2d_{3.2} pairwise anticomplete members of the first type: the separator Y^\widehat{Y} hits each of them, and choosing one vertex from each intersection gives an independent set in the separator. Consequently, HS^1,S^2\mathcal{H}_{\widehat{S}_1,\widehat{S}_2} has no d3.2+2b+1d_{3.2}+2b+1 pairwise anticomplete members.

Apply Lemma 3.3 to each HS1,S2\mathcal{H}_{S_1,S_2} in G[W]G[W] with parameters t,s,d3.2+2b+1t,s,d_{3.2}+2b+1. Since the second outcome is impossible for the pair S^1,S^2\widehat{S}_1,\widehat{S}_2, at least one call returns a hitting set YY for some HS1,S2\mathcal{H}_{S_1,S_2} with α(Y)≤d3.4\alpha(Y) \leq d_{3.4}. As Lemma 3.3 was invoked in G[W]G[W], we have that Y⊆WY \subseteq W. Thus, by Claim 3.4.1, YY is an S1S_1–S2S_2-separator, and we can return S1,S2,YS_1,S_2,Y as the second outcome of Lemma 3.4.

Note that there are (b2)\binom{b}{2} pairs S1,S2S_1,S_2 and each family can be constructed by exhaustively enumerating paths of length at most tt. 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 St,t,tS_{t,t,t}-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 St,t,tS_{t,t,t}-free graph GG and a mass function μ\mu, one can in polynomial time find S⊆V(G)S \subseteq V(G) with ∣S∣≤3t+11|S| \leq3t+11 and a rigid extended strip decomposition of G−NG[S]G-N_G[S] that is balanced for μ\mu.

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 s,ts,t, there is a computable constant a3.6a_{3.6} and a polynomial-time algorithm which, given an nn-vertex (St,t,t,Ks,s)(S_{t,t,t},K_{s,s})-free graph GG with mass function μ\mu, finds ZZ with α(Z)≤a3.6\alpha(Z) \leq a_{3.6} and an extended strip decomposition of G−ZG-Z that is balanced for μ\mu and whose host has O(n)O(n) vertices and edges.

Proof. Define the following constants depending only on s,ts,t:

b=3t+11,c=c3.4(b,s,t),d=d3.4(b,s,t),a3.6=2c+d.\begin{aligned} b &= 3t+11,\\ c &= c_{3.4}(b,s,t),\\ d &= d_{3.4}(b,s,t),\\ a_{3.6} &= 2c+d. \end{aligned}

Throughout the execution of the algorithm, we will maintain a bb-system S\mathcal{S}; the algorithm starts with S=∅\mathcal{S}=\varnothing. With each S∈SS\in\mathcal{S} we store a set XSX_S with α(XS)≤c\alpha(X_S)\le c and a rigid extended strip decomposition (HS,ηS)(H_S,\eta_S) of G−(XS∪NG[S])G-(X_S\cup N_G[S]) that is balanced for μ\mu. By Proposition 2.1(3), every stored host has at most 2n2n vertices and nn edges.

Iteratively, we apply Lemma 3.4 to the current system S\mathcal{S}.

Suppose first that the application returns the second outcome, i.e., two anticomplete members S1,S2∈SS_1,S_2\in\mathcal{S} and an S1S_1–S2S_2-separator YY with α(Y)≤d\alpha(Y)\le d. Define Z=XS1∪XS2∪YZ=X_{S_1}\cup X_{S_2}\cup Y, so α(Z)≤2c+d=a3.6\alpha(Z)\le2c+d=a_{3.6}. No component of G−ZG-Z meets both NG[S1]N_G[S_1] and NG[S2]N_G[S_2]: such a component, together with an endpoint in each SiS_i, would give an S1S_1–S2S_2-path in G−YG-Y. Let V1V_1 be the union of the components avoiding NG[S1]N_G[S_1], and set V2=V(G−Z)∖V1V_2=V(G-Z)\setminus V_1. Then V1,V2V_1,V_2 are anticomplete and

Vi⊆V(G−(XSi∪NG[Si]))for i∈{1,2}.V_i\subseteq V\bigl(G-(X_{S_i}\cup N_G[S_i])\bigr)\qquad\text{for }i\in\{1,2\}.

Restrict (HSi,ηSi)(H_{S_i},\eta_{S_i}) to ViV_i and take the disjoint union of the two decompositions. By Proposition 2.1(1) and (2), this is a decomposition of G−ZG-Z, and each new particle is contained in a stored particle. Hence the result is balanced for μ\mu. Restriction leaves the hosts unchanged, so their union has at most 4n4n vertices and at most 2n2n edges. Return ZZ and this decomposition, and terminate. We remark that the restrictions may destroy rigidity, but the outcome of this step is never stored in S\mathcal{S}.

So, suppose that the application of Lemma 3.4 returns the first outcome, i.e., a hitting set XX for S\mathcal{S} with α(X)≤c\alpha(X)\le c. Apply Theorem 3.5 to G−XG-X with the restriction of μ\mu. We obtain a set S⊆V(G)∖XS\subseteq V(G)\setminus X with ∣S∣≤b|S|\le b and a rigid extended strip decomposition (H,η)(H,\eta) of (G−X)−NG−X[S]=G−(X∪NG[S])(G-X)-N_{G-X}[S]=G-(X\cup N_G[S]) whose particles have mass at most μ(G−X)/2≤μ(G)/2\mu(G-X)/2\le\mu(G)/2. If S=∅S=\varnothing, return Z=XZ=X and (H,η)(H,\eta), and terminate. This satisfies the required independence-number bound since α(X)≤c≤a3.6\alpha(X)\le c\le a_{3.6}, and the host has at most 2n2n vertices and nn edges by rigidity.

Otherwise, add SS to S\mathcal{S}, set XS=XX_S=X and (HS,ηS)=(H,η)(H_S,\eta_S)=(H,\eta), and proceed to the next iteration. Note that SS was not already a member of S\mathcal{S}: it is disjoint from XX, whereas every previous member meets XX. Thus every nonterminating iteration adds a new member to S\mathcal{S}, and there are at most nbn^b 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 s≥2s\ge2 and let (H,η)(H,\eta) be an extended strip decomposition of a Ks,sK_{s,s}-free graph GG. Call a vertex set small if its independence number is at most s−1s-1, and large otherwise. At most one interface at a given host vertex is large: two such interfaces would contain independent ss-vertex sets complete to one another, inducing a Ks,sK_{s,s}. For every x∈V(H)x\in V(H), define

small⁡(x)=⋃xy∈E(H)η(xy,x) smallη(xy,x),Small=⋃x∈V(H)small⁡(x).(1)\operatorname{small}(x)=\bigcup_{\substack{xy\in E(H)\\ \eta(xy,x)\ \mathrm{small}}}\eta(xy,x),\qquad \mathrm{Small}=\bigcup_{x\in V(H)}\operatorname{small}(x). \tag*{(1)}

Thus Small\mathrm{Small} is the union of all small interfaces. As all interfaces at xx are complete to each other, we have α(small⁡(x))≤s−1\alpha(\operatorname{small}(x))\le s-1. However, the independence number of Small\mathrm{Small} might be arbitrarily large. For fixed ss, sets small⁡(x)\operatorname{small}(x) and Small\mathrm{Small} can be found in polynomial time by exhaustively enumerating ss-vertex sets in each interface.

Lemma 3.7. Let s≥2s\ge2 be an integer, let (H,η)(H,\eta) be an extended strip decomposition of a Ks,sK_{s,s}-free graph GG. Let small⁡(x)\operatorname{small}(x) for each x∈V(H)x\in V(H) and Small\mathrm{Small} be defined as in (1). Then the following hold.

(1) α(Small∩A)≤2(s−1)\alpha(\mathrm{Small}\cap A)\le2(s-1) for every particle AA of (H,η)(H,\eta).

(2) Every component DD of G−SmallG-\mathrm{Small} is contained in a particle of (H,η)(H,\eta) and satisfies α(NG(D))≤2(s−1)\alpha(N_G(D))\le2(s-1).

Proof. The set Small\mathrm{Small} lies entirely in the union of edge atoms, and, for every edge xy∈E(H)xy\in E(H), Small∩η(xy)\mathrm{Small}\cap\eta(xy) is the union of the small interfaces of xyxy. Hence α(Small∩η(xy))≤2(s−1)\alpha(\mathrm{Small}\cap\eta(xy))\le2(s-1). Since every particle meets at most one edge atom, this proves item (1).

To prove item (2), let DD be a component of G−SmallG-\mathrm{Small}; in particular, NG(D)⊆SmallN_G(D)\subseteq\mathrm{Small}.

Claim 3.7.1. The component DD is contained in a particle of (H,η)(H,\eta).

Proof of Claim 3.7.1: Let (H,η′)(H,\eta') be the extended strip decomposition of G−SmallG-\mathrm{Small} obtained by restricting (H,η)(H,\eta) to V(G)∖SmallV(G)\setminus\mathrm{Small}, as in Proposition 2.1(1). Every small interface becomes empty, so at each host vertex at most one interface of (H,η′)(H,\eta') 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 (H,η′)(H,\eta') are anticomplete. Similarly, all neighbors of a vertex atom η′(x)\eta'(x) lie in the unique nonempty interface at xx, if it exists, so η′(x)\eta'(x) has neighbors in at most one edge atom. A triangle atom η′(xyz)\eta'(xyz) has neighbors only in the edge atoms η′(xy)\eta'(xy), η′(xz)\eta'(xz), and η′(yz)\eta'(yz). Moreover, it has a neighbor in η′(xy)\eta'(xy) only if both η′(xy,x)\eta'(xy,x) and η′(xy,y)\eta'(xy,y) are nonempty, and analogously for xzxz and yzyz. As any two of the edges xyxy, xzxz, and yzyz of HH share a vertex, and at each host vertex at most one interface of (H,η′)(H,\eta') is nonempty, at most one of these three edges has both of its interfaces in (H,η′)(H,\eta') nonempty. Hence η′(xyz)\eta'(xyz) also has neighbors in at most one edge atom. Distinct vertex and triangle atoms are anticomplete. Consequently, as DD is connected, it meets at most one edge atom of (H,η′)(H,\eta'). If DD meets η′(xy)\eta'(xy), then, as DD is connected and meets no other edge atom, every vertex or triangle atom meeting DD has a neighbor in η′(xy)\eta'(xy). Thus every such atom is η′(x)\eta'(x), η′(y)\eta'(y), or η′(xyz)\eta'(xyz) for some xyz∈T(H)xyz\in T(H), and hence D⊆AxyxyD\subseteq A^{xy}_{xy}. Otherwise, DD 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, DD is contained in a particle of (H,η)(H,\eta).

Thus, it remains to show that α(NG(D))≤2(s−1)\alpha(N_G(D))\leq2(s-1). Let us first consider the case when DD meets an edge atom η(xy)\eta(xy) for some xy∈E(H)xy\in E(H).

Claim 3.7.2. If DD meets η(xy)\eta(xy) for some xy∈E(H)xy\in E(H), then NG(D)⊆small(x)∪small(y)N_G(D)\subseteq\mathrm{small}(x)\cup\mathrm{small}(y). In particular, α(NG(D))≤α(small(x))+α(small(y))≤2(s−1)\alpha(N_G(D))\leq\alpha(\mathrm{small}(x))+\alpha(\mathrm{small}(y))\leq2(s-1).

Proof of Claim 3.7.2: Every particle meeting η(xy)\eta(xy) is one of Axy⊥A^{\perp}_{xy}, AxyxA^{x}_{xy}, AxyyA^{y}_{xy}, and AxyxyA^{xy}_{xy}, and all of them are contained in AxyxyA^{xy}_{xy}. Hence D⊆AxyxyD\subseteq A^{xy}_{xy} by Claim 3.7.1. Neighbors of DD in η(xy)\eta(xy) lie in Small∩η(xy)\mathrm{Small}\cap\eta(xy), and thus in small(x)∪small(y)\mathrm{small}(x)\cup\mathrm{small}(y). Since NG(D)⊆SmallN_G(D)\subseteq\mathrm{Small}, every neighbor of DD lies in an edge atom. By the definition of an extended strip decomposition, every neighbor of DD outside η(xy)\eta(xy) thus lies in an interface η(xz,x)\eta(xz,x) with z∈NH(x)∖{y}z\in N_H(x)\setminus\{y\} or in an interface η(yz,y)\eta(yz,y) with z∈NH(y)∖{x}z\in N_H(y)\setminus\{x\}. By symmetry, let ww be a neighbor of DD of the first kind; we show that w∈small(x)w\in\mathrm{small}(x). The only vertices of AxyxyA^{xy}_{xy} that can be adjacent to ww lie in η(x)\eta(x), in η(xy,x)\eta(xy,x), or in η(xyz)\eta(xyz) if xyz∈T(H)xyz\in T(H), so DD meets one of these sets. In fact, DD meets η(xy,x)\eta(xy,x). Indeed, all neighbors of η(x)\eta(x) and of η(xyz)\eta(xyz) in AxyxyA^{xy}_{xy} lie in η(xy,x)\eta(xy,x), and if DD meets one of these two atoms, then it also contains a neighbor of this atom, as DD is connected and meets η(xy)\eta(xy). As D∩Small=∅D\cap\mathrm{Small}=\varnothing, the interface η(xy,x)\eta(xy,x) is not contained in Small\mathrm{Small}, so it is large. Since at most one interface at xx is large, η(xz,x)\eta(xz,x) is small, and hence w∈small(x)w\in\mathrm{small}(x). Now, the bound on α(NG(D))\alpha(N_G(D)) follows from the bound on α(small(x))\alpha(\mathrm{small}(x)) and α(small(y))\alpha(\mathrm{small}(y)).

Now, consider the case when DD meets no edge atom, i.e., it is contained in a single vertex or triangle atom. Since NG(D)⊆SmallN_G(D)\subseteq\mathrm{Small}, the definition of an extended strip decomposition implies the following:

  • if D⊆η(x)D\subseteq\eta(x) for some x∈V(H)x\in V(H), then NG(D)N_G(D) is contained in the union of the sets Small∩η(xy,x)\mathrm{Small}\cap\eta(xy,x) over all y∈NH(x)y\in N_H(x);

  • if D⊆η(xyz)D\subseteq\eta(xyz) for some xyz∈T(H)xyz\in T(H), then NG(D)N_G(D) is contained in the union of the sets Small∩η(xy,x)∩η(xy,y)\mathrm{Small}\cap\eta(xy,x)\cap\eta(xy,y), Small∩η(xz,x)∩η(xz,z)\mathrm{Small}\cap\eta(xz,x)\cap\eta(xz,z), and Small∩η(yz,y)∩η(yz,z)\mathrm{Small}\cap\eta(yz,y)\cap\eta(yz,z).

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 NG(D)N_G(D) is contained in one of these sets. Moreover, each of these sets is contained in Small∩A\mathrm{Small}\cap A for some full edge particle AA, so its independence number is at most 2(s−1)2(s-1) by item (1). Therefore α(NG(D))≤2(s−1)\alpha(N_G(D))\leq2(s-1), which completes the proof of item (2). ∎

Excluding a single long claw

In this section we prove Theorem 1.1 for F=St,t,tF=S_{t,t,t}, 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 t≥1t \ge1, s≥2s \ge2; we treat them as fixed constants. Fix an ambient (St,t,t,Ks,s)(S_{t,t,t},K_{s,s})-free weighted graph (G,w)(G,\mathbf{w}), 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 (V′,T)(V',T) of disjoint subsets of V(G)V(G), and its graph is G′=G[V′∪T]G'=G[V' \cup T] with weights w\mathbf{w}. The vertices of TT are called terminals and the set V′V' is called the interior of the instance.

The goal for an instance (V′,T)(V',T) is to compute the auxiliary table entries Tab⁡[V′,T,I]\operatorname{Tab}[V',T,I] for all independent sets I⊆TI \subseteq T. Each entry stores the largest weight that the interior can contribute when precisely the terminals in II are selected:

Tab⁡[V′,T,I]=max⁡{w(J)∣J⊆V′, I∪J is independent in G}.\operatorname{Tab}[V',T,I] = \max\{\mathbf{w}(J) \mid J \subseteq V',\ I \cup J\text{ is independent in }G\}.

In particular, Tab⁡[V(G),∅,∅]=α(G,w)\operatorname{Tab}[V(G),\varnothing,\varnothing]=\alpha(G,\mathbf{w}).

For a set Z⊆V′∪TZ \subseteq V' \cup T and an independent set J⊆T∪ZJ \subseteq T \cup Z, define WJ=V′∖(Z∪NG(J))W_J=V'\setminus(Z\cup N_G(J)). Then, for every independent I⊆TI \subseteq T,

Tab⁡[V′,T,I]=max⁡J⊆T∪Z independentJ∩T=I[w(J∖T)+α(G[WJ],w)].(2)\operatorname{Tab}[V',T,I] = \max_{\substack{J\subseteq T\cup Z\text{ independent}\\J\cap T=I}} \left[\mathbf{w}(J\setminus T)+\alpha(G[W_J],\mathbf{w})\right]. \tag*{(2)}

Indeed, after fixing the selected vertices JJ of T∪ZT\cup Z, the remaining set is an independent set in G[WJ]G[W_J].

Child instances

Fix an instance (V′,T)(V',T) with graph G′=G[V′∪T]G'=G[V'\cup T]. We define child instances whose tables determine Tab⁡[V′,T,⋅]\operatorname{Tab}[V',T,\cdot]. Let Z⊆V′∪TZ\subseteq V'\cup T and let (H,η)(H,\eta) be an extended strip decomposition of G′−ZG'-Z. Let Small⁡\operatorname{Small} be defined as in (1), and define S=T∪Z∪Small⁡S=T\cup Z\cup\operatorname{Small}. For every particle AA, let Q(A)\mathcal{Q}(A) consist of the vertex sets of the components of G[A∖S]G[A\setminus S]. Define Q=⋃AQ(A)\mathcal{Q}=\bigcup_A\mathcal{Q}(A), where the union ranges over all particles of (H,η)(H,\eta). For each R∈QR\in\mathcal{Q}, define its boundary BR=NG(R)∩SB_R=N_G(R)\cap S and the child instance (R,BR)(R,B_R), whose interior is RR. Note that even when R∈Q(A)R\in\mathcal{Q}(A), its boundary BRB_R need not be contained in AA. We compute each child table once, even if RR occurs for several particles.

Clearly, one can construct Q\mathcal{Q} and all child instances in time polynomial in ∣V′∪T∣+∣V(H)∣|V'\cup T|+|V(H)|.

Lemma 4.1. Every vertex of V′V' belongs to at most four members of Q\mathcal{Q}. Consequently, we have

∑R∈Q∣R∣≤4∣V′∣.\sum_{R\in\mathcal{Q}}|R|\le4|V'|.

Proof. Every particle is contained in (V′∪T)∖Z(V'\cup T)\setminus Z and T∪Z⊆ST\cup Z\subseteq S, so every member of Q\mathcal{Q} is a subset of V′∖SV'\setminus S. Hence the second statement follows from the first, and it suffices to prove the first statement for a fixed vertex v∈V′∖Sv\in V'\setminus S. For every particle AA containing vv, let CAC_A be the vertex set of the component of G[A∖S]G[A\setminus S] containing vv. Then CAC_A is the unique member of Q(A)\mathcal{Q}(A) containing vv, so the members of Q\mathcal{Q} containing vv are exactly the sets CAC_A, where AA ranges over the particles containing vv.

If vv lies in an edge atom η(xy)\eta(xy), then every particle containing vv is one of Axy⊥A_{xy}^{\perp}, AxyxA_{xy}^{x}, AxyyA_{xy}^{y}, and AxyxyA_{xy}^{xy}. If vv lies in a triangle atom η(xyz)\eta(xyz), then every particle containing vv is one of AxyzA_{xyz}, AxyxA_{xy}^{x}, AxyyA_{xy}^{y}, AxzxA_{xz}^{x}, and AyzyA_{yz}^{y}. In both cases, there are at most four sets CAC_A.

It remains to consider the case that vv lies in a vertex atom η(x)\eta(x) for some x∈V(H)x\in V(H). By the definition of particles, the particles containing vv are exactly the following:

  • the vertex particle AxA_x, and

  • the half-edge particle AxyxyA_{xy}^{xy} and the full edge particle AxyxyA_{xy}^{xy} for each y∈NH(x)y\in N_H(x).

We show that at most three of the sets CAC_A are distinct.

By the definition of an extended strip decomposition, every vertex of NG′−Z(η(x))N_{G'-Z}(\eta(x)) lies in an interface η(xy,x)\eta(xy,x) for some y∈NH(x)y \in N_H(x). Let y∈NH(x)y \in N_H(x) be such that η(xy,x)\eta(xy,x) is small, and let A∈{Axyx,Axyxy}A \in\{A_{xy}^x,A_{xy}^{xy}\}. Since AA is disjoint from all edge atoms other than η(xy)\eta(xy), we have NG′−Z(η(x))∩A⊆η(xy,x)⊆Small⊆SN_{G'-Z}(\eta(x)) \cap A \subseteq\eta(xy,x) \subseteq\mathrm{Small} \subseteq S by (1). Thus η(x)\eta(x) is anticomplete to A∖(S∪η(x))A \setminus(S \cup\eta(x)), and since CAC_A is connected and contains v∈η(x)v \in\eta(x), we obtain CA⊆η(x)C_A \subseteq\eta(x). As Ax=η(x)⊆AA_x=\eta(x)\subseteq A, this yields CA=CAxC_A=C_{A_x}.

Finally, recall that at most one interface at xx is large. Hence every set CAC_A equals CAxC_{A_x}, except possibly CAxyxC_{A_{xy}^x} and CAxyxyC_{A_{xy}^{xy}} for the unique y∈NH(x)y \in N_H(x) with η(xy,x)\eta(xy,x) large, if such a yy exists. Thus at most three of the sets CAC_A are distinct.

Lemma 4.2. Given the child tables, we can compute Tab⁡[V′,T,⋅]\operatorname{Tab}[V',T,\cdot] in time polynomial in ∣V′∪T∣+∣V(H)∣|V' \cup T|+|V(H)| per independent subset of T∪ZT\cup Z.

Proof. Fix an independent set J⊆T∪ZJ \subseteq T \cup Z and let WJW_J be as in (2). For every particle AA, we have

α(A∩WJ,w)=max⁡I⊆Small∩A∩WJI independent[w(I)+∑R∈Q(A)Tab⁡[R,BR,(I∪J)∩BR]].(3)\alpha(A \cap W_J,w)=\max_{\substack{I\subseteq\mathrm{Small}\cap A\cap W_J\\ I\ \text{independent}}}\left[w(I)+\sum_{R\in\mathcal{Q}(A)}\operatorname{Tab}[R,B_R,(I\cup J)\cap B_R]\right]. \tag*{(3)}

Indeed, after fixing II, the remaining choices lie in the pairwise anticomplete components R∈Q(A)R\in\mathcal{Q}(A). As I∪J⊆SI\cup J\subseteq S, the choices in each RR must be compatible precisely with (I∪J)∩BR(I\cup J)\cap B_R, as encoded by the corresponding table entry. By Lemma 3.7[1], there are ∣V′∪T∣O(s)|V'\cup T|^{O(s)} choices of II. Restrict (H,η)(H,\eta) to WJW_J using Proposition 2.1[1], and apply Theorem 2.2 with the values in (3) to compute α(G[WJ],w)\alpha(G[W_J],w). 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 s,t≥1s,t\geq1, there is a polynomial-time algorithm which, given an (St,t,t,Ks,s)(S_{t,t,t},K_{s,s})-free graph GG and a weight function w:V(G)→R≥0w:V(G)\to\mathbb{R}_{\geq0}, returns a maximum-weight independent set in (G,w)(G,w).

Proof. Let n=∣V(G)∣n=|V(G)|. If n≤1n\leq1 or s=1s=1, the result is obvious. Thus suppose n≥2n\geq2 and s≥2s\geq2, and define k=a3.6+2(s−1)k=a_{3.6}+2(s-1); this constant depends only on s,ts,t.

Throughout the recursion, we compute the table Tab⁡[V′,T,⋅]\operatorname{Tab}[V',T,\cdot] for an instance (V′,T)(V',T) while maintaining α(T)≤6k\alpha(T)\leq6k. The initial call uses V′=V(G)V'=V(G) and T=∅T=\varnothing. At each call, define G′=G[V′∪T]G'=G[V'\cup T]. If ∣V′∣≤1|V'|\leq1, compute each table entry directly. Otherwise proceed as follows.

  1. Enumerate all independent subsets of TT of size at most 6k6k. Choose one of maximum cardinality, say JJ, and write h=∣J∣=α(T)h=|J|=\alpha(T).

  1. If h≤5kh\leq5k, let μ\mu be the indicator mass function of V′V'. Otherwise, let μ\mu be the indicator mass function of JJ. Apply Lemma 3.6 to G′G' with this mass function, obtaining ZZ with α(Z)≤a3.6\alpha(Z)\leq a_{3.6} and a balanced extended strip decomposition of G′−ZG'-Z with a host of linear size. Define its small-interface set Small\mathrm{Small} as in (1).

  1. Construct the distinct children (R,BR)(R,B_R) as in § 4.2 and recursively compute Tab⁡[R,BR,⋅]\operatorname{Tab}[R,B_R,\cdot], once per child.

  1. Compute the parent table Tab⁡[V′,T,⋅]\operatorname{Tab}[V',T,\cdot] using Lemma 4.2.

We verify that the terminal bound is preserved and that the recursion terminates. For a child (R,BR)(R,B_R), let DD be the component of G′−(Z∪Small)G'-(Z\cup\mathrm{Small}) containing RR. Since NG′(D)⊆Z∪NG′−Z(D)N_{G'}(D)\subseteq Z\cup N_{G'-Z}(D), Lemma 3.7[2] gives

α(NG′(D))≤k,BR⊆(T∩D)∪NG′(D).\alpha(N_{G'}(D))\leq k,\qquad B_R\subseteq(T\cap D)\cup N_{G'}(D).

If h≤5kh\leq5k, the decomposition is balanced for the indicator mass function of the interior. Since DD is contained in a particle, we obtain

∣R∣≤∣D∖T∣≤∣V′∣/2,α(BR)≤α(T∩D)+k≤h+k≤6k.(4)|R|\leq|D\setminus T|\leq|V'|/2,\qquad\alpha(B_R)\leq\alpha(T\cap D)+k\leq h+k\leq6k. \tag*{(4)}

Suppose instead that h>5kh > 5k. The decomposition is balanced for the indicator mass function of JJ, so ∣J∩D∣≤h/2|J \cap D| \le h/2. Replacing J∩NG′[D]J \cap N_{G'}[D] by any independent set in T∩DT \cap D preserves independence, as J∖NG′[D]J \setminus N_{G'}[D] is anticomplete to DD. Since JJ is a maximum independent set of TT, this gives

α(BR)≤α(T∩D)+k≤∣J∩D∣+∣J∩NG′(D)∣+k≤h/2+2k≤5k.\alpha(B_R) \le\alpha(T \cap D) + k \le|J \cap D| + |J \cap N_{G'}(D)| + k \le h/2 + 2k \le5k.

Thus the terminal bound is preserved, and any call that does not halve the interior has children with terminal independence number at most 5k5k. Every two recursion levels therefore halve the interior, so the recursion terminates. Each child graph is induced in GG and hence remains (St,t,t,Ks,s)(S_{t,t,t}, K_{s,s})-free. Correctness now follows by induction using Lemma 4.2. At the root, Tab⁡[V(G),∅,∅]=α(G,w)\operatorname{Tab}[V(G), \varnothing, \varnothing] = \alpha(G,w).

The recursion has depth O(log⁡n)O(\log n), and Lemma 4.1 bounds the sum of the interior sizes at depth ℓ\ell by 4ℓn4^\ell n. 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 α(T)≤6k\alpha(T) \le6k and α(T∪Z)≤7k\alpha(T \cup Z) \le7k 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 s≥1s \ge1 and F∈FF \in\mathcal{F}, there is a polynomial-time algorithm which, given an (F,Ks,s)(F, K_{s,s})-free graph GG and a weight function w:V(G)→R≥0w : V(G) \to\mathbb{R}_{\ge0}, returns a maximum-weight independent set in (G,w)(G,w).

Proof. Let dd be the number of components of FF and let t=max⁡{1,∣V(F)∣}t = \max\{1, |V(F)|\}. Then FF is an induced subgraph of dSt,t,tdS_{t,t,t}, and hence every (F,Ks,s)(F, K_{s,s})-free graph is also (dSt,t,t,Ks,s)(dS_{t,t,t}, K_{s,s})-free.

Define b=3t+1b = 3t + 1, and let S\mathcal{S} consist of the vertex sets of all induced copies of St,t,tS_{t,t,t} in GG. This is a bb-system that can be constructed in polynomial time by enumerating all bb-vertex subsets of V(G)V(G). Apply Lemma 3.3 to S\mathcal{S} with parameters b,s,db,s,d. The second outcome gives dd pairwise anticomplete induced copies of St,t,tS_{t,t,t}, inducing dSt,t,tdS_{t,t,t} in GG. Thus we obtain a hitting set XX with α(X)≤c3.3(b,s,d)\alpha(X) \le c_{3.3}(b,s,d). Since XX meets every induced copy of St,t,tS_{t,t,t}, the graph G−XG-X is St,t,tS_{t,t,t}-free.

Clearly,

α(G,w)=max⁡J⊆XJ independent[w(J)+α(G−(X∪NG(J)),w)].\alpha(G,w) = \max_{\substack{J \subseteq X \\ J\ \text{independent}}} \left[w(J) + \alpha(G - (X \cup N_G(J)),w)\right].

The bound on α(X)\alpha(X) lets us enumerate all independent subsets J⊆XJ \subseteq X in polynomial time. For each JJ, the residual graph is induced in G−XG-X and hence is (St,t,t,Ks,s)(S_{t,t,t}, K_{s,s})-free. Solve MWIS in this graph using Theorem 4.3, and add JJ to the resulting independent set. Returning the heaviest set obtained in this way gives a maximum-weight independent set in GG. Since d,s,td,s,t are fixed, the construction of S\mathcal{S}, the application of Lemma 3.3, and all residual computations take polynomial time. □\square

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 FF-free graphs, for F∈FF \in\mathcal{F}, 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 F∈FF \in\mathcal{F} and integer s≥1s \ge1, can MWIS be solved in polynomial time in (F,Ks)(F,K_s)-free graphs?

Even the special case where FF is a path remains open in general.

Problem 6.2. For every fixed pair of integers t,s≥1t,s \ge1, can MWIS be solved in polynomial time in (Pt,Ks)(P_t,K_s)-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 t=7t=7 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [18]S. Hajebi and S. Spirkl. Tree-alpha and excluding finitely many graphs. CoRR, abs/2605.01223, 2026.arxiv.org/abs/2605.01223
  19. [19]R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer US, 1972.
  20. [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. [21]D. Kühn and D. Osthus. Induced subdivisions in Kₛ,ₛ-free graphs of large average degree. Combinatorica, 24:287–304, 2004.
  22. [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. [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. [24]F. Maffray and L. Pastor. Maximum weight stable set in (P₇, bull)-free graphs. CoRR, abs/1611.09663, 2016.
  25. [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. [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. [27]R. Mosca. Stable sets of maximum weight in (P₇, banner)-free graphs. Discrete Mathematics, 308(1):20–33, 2008.DOI
  28. [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. [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. [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

Paper details

vlnc:W_zjzvkv4d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, Claude

View statement
Looking for related papers…
Contents