Max Weight Independent Set in sparse graphs with no long claws¹¹1Parts of this work appeared in the proceedings of SODA 2021 [1] and STACS 2024 [3]

The study of the complexity of MWIS in restricted graph classes is a central topic in algorithmic graph theory [2, 27, 53, 18, 5, 8]. Particular attention is given to classes that are hereditary, i.e., closed under vertex deletion. Among such classes a special role is played by ones defined by forbidding certain substructures. For graphs $G$ and $H$, we say that $G$ is $H$-free if it does not contain $H$ as an induced subgraph.

In what follows, for $t\geqslant 1$, by $P_{t}$ we denote the $t$-vertex path. For integers $a,b,c\geqslant 1$, by $S_{a,b,c}$ we denote the graph obtained from the three-leaf star (i.e., the claw) by subdividing the three edges $a-1$, $b-1$, and $c-1$ times, respectively. Alternatively, we may think of $S_{a,b,c}$ as the graph obtained from paths $P_{a+1},P_{b+1}$, and $P_{c+1}$ by identifying one endvertex of each path. By $dS_{a,b,c}$ we denote the graph with $d$ components, each of which is isomorphic to $S_{a,b,c}$.

Let $\mathcal{S}$ be the family of subcubic forests $H$ whose every component has at most one vertex of degree 3, i.e., whose every component is either a path or a subdivided claw.

The complexity study of MWIS in $H$-free graphs dates back to the early 1980s and the work of Alekseev [4], who observed that for most graphs $H$ the problem remains NP-hard. Indeed, let us discuss the hard cases. First, MIS (and thus MWIS) is NP-hard in subcubic graphs [22], which are $H$-free whenever $H$ has a vertex of degree at least 4. For the remaining cases we will use the so-called Poljak construction [50]: If $G^{\prime}$ is obtained from $G$ by subdividing one edge twice, then $\alpha(G^{\prime})=\alpha(G)+1$. Thus, if $G^{p}$ denotes the graph obtained from $G$ by subdividing each edge exactly $2p$ times, then $\alpha(G^{p})=\alpha(G)+p\cdot|E(G)|$. Now observe that if $H$ has a cycle or two vertices of degree three in one component, then $G^{|V(H)|}$ is $H$-free. Consequently, for such graph $H$, MIS is NP-hard in $H$-free graphs. Let us point out that the above hardness reductions imply that MIS cannot even be solved in subexponential time unless the Exponential-Time Hypothesis (ETH) fails.

Summing up, the only graphs $H$ for which we may hope for a polynomial-time (or even subexponential-time) algorithm for MWIS in $H$-free graphs are precisely the graphs in $\mathcal{S}$.

The complexity of MWIS in $H$-free graphs when $H\in\mathcal{S}$ remains one of the most challenging and important problems in algorithmic graph theory. Despite significant attention received from the graph theory and the theoretical computer science communities, only partial results are known. Let us discuss them.

First, consider the case that $H=P_{t}$ for some $t$. Since $P_{4}$-free graphs, also known as cographs, have very rigid structure (in particular, they have clique-width at most 2), the polynomial-time algorithm for this class of graphs is rather simple [19]. However, already for $P_{5}$-free graphs the situation is much more complicated. The existence of a polynomial-time algorithm for $P_{5}$-free graphs was a long-standing open problem that was finally resolved in the affirmative in 2014 by Lokshtanov, Vatshelle, and Villanger [35] using the framework of potential maximal cliques. Later, using the same approach but with significantly more technical effort, Grzesik, Klimošová, Pilipczuk, and Pilipczuk [26] obtained a polynomial-time algorithm for $P_{6}$-free graphs. The case of $P_{7}$-free graphs remains open.

However, some interesting algorithmic results can be obtained if we relax our notion of an efficient algorithm. First, it was shown by Bacsó et al. [7] that for every fixed $t$, MWIS can be solved in subexponential time $2^{\mathcal{O}(\sqrt{n\log n})}$ for $P_{t}$-free graphs (by $n$ we always denote the number of vertices of the instance graph). Another subexponential-time algorithm, with worse running time, was obtained independently by Brause [13]. While these results do not rule out the possibility that the problem is NP-hard, let us recall that, assuming the ETH, subexponential algorithms for MWIS in $H$-free graphs cannot exist if $H\notin\mathcal{S}$. Later, Chudnovsky et al. [16, 15] showed that for every fixed $t$, the problem admits a QPTAS in $P_{t}$-free graphs. Finally, a very recent breakthrough result by Gartland and Lokshtanov [23] shows that for every fixed $t$, the problem can be solved in quasipolynomial time $n^{\mathcal{O}(\log^{3}n)}$; see also a slightly simpler algorithm by Pilipczuk, Pilipczuk, and Rzążewski [49] with running time $n^{\mathcal{O}(\log^{2}n)}$. Note that this means that if for some $t$,MWIS is NP-hard for $P_{t}$-free graphs, then all problems in NP can be solved in quasipolynomial time. While this does yet not imply that P = NP, it still seems rather unlikely according to our current understanding of complexity theory.

Now let us turn to the case when $H$ is a subdivided claw. The simplest subdivided claw is the claw $S_{1,1,1}=K_{1,3}$. Claw-free graphs appear to be closely related to line graphs [17] and thus a polynomial-time algorithm for MWIS in claw-free graphs can be obtained by a modification of the well-known augmenting path approach for finding a maximum-weight matching [51, 43] (i.e., a maximum-weight independent set in a line graph). Let us highlight the close relation of claw-free graphs and line graphs, as it will play an important role in our paper. The next smallest subdivided claw is the fork, i.e., $S_{2,1,1}$. A polynomial-time algorithm for MIS in fork-free graphs was obtained by Alekseev [6]. Later it was extended to the MWIS problem by Lozin and Milanič [36]. For disconnected $H$, it is known that MWIS is polynomial-time-solvable in $dS_{1,1,1}$-free graphs, for every fixed $d$ [10]. The existence of polynomial-time algorithms in the next simplest (connected) cases, i.e., $H=S_{3,1,1}$ and $H=S_{2,2,1}$, is wide open.

Again, some interesting results can be obtained if we look beyond polynomial-time algorithms. Chudnovsky et al. [16, 15] proved that for every subdivided claw $H$, the MWIS problem in $H$-free graphs admits a QPTAS and a subexponential-time algorithm working in time $n^{\mathcal{O}(n^{8/9})}$. We point out that the arguments used for the case when $H$ is a subdivided claw are significantly more complicated and technically involved than their counterparts for $P_{t}$-free graphs. These results were then simplified and improved by Majewski et al. [42]: They obtained another (faster) QPTAS and a subexponential-time algorithm with running time $n^{\mathcal{O}(\sqrt{n}\log n)}$. Finally, very recently, Gartland et al.  [24] announced a quasipolynomial-time algorithm for MWIS in $H$-free graphs for every $H\in\mathcal{S}$.

More tractability results can be obtained if we put some additional restrictions on the instance graph. In particular, there is a long line of research concerning graphs excluding a fixed (but still small) path or a subdivided claw and, simultaneously, some other small graphs, see e.g. [34, 11, 25, 39, 41, 45, 37, 38, 28, 44, 46, 47, 48, 12]. A slightly different direction was considered by Lozin, Milanič, and Purcell [37], who proved that for every fixed $t$,MWIS is polynomial-time solvable in subcubic $S_{t,t,1}$-free graphs. Later, Lozin, Monnot, and Ries [38] showed a polynomial time algorithm for subcubic $S_{2,2,2}$-free graphs. Finally, Harutyunya et al. [28] generalized both these results by providing a polynomial-time algorithm for subcubic $S_{2,t,t}$-free graphs, for any fixed $t$.

We remark that the case when $H$ is a subdivided claw (or, more precisely, is in $\mathcal{S}$ and contains at least one component which is not a path) is the only case where the restriction to bounded degree graphs leads to an interesting problem. Indeed, the already mentioned hardness reduction of Alekseev [4] shows that if $H\notin\mathcal{S}$, then MIS is NP-hard even in subcubic $H$-free graphs. On the other hand, if $H$ is a forest of paths, then $H$-free graphs of bounded degree are of constant size and thus of little interest.

In this work, we continue and significantly extend the study of the complexity of MWIS in $H$-free graphs with additional restrictions, where $H\in\mathcal{S}$.

As a warm-up, we present a polynomial-time algorithm for $H$-free graphs of bounded degree, where $H\in\mathcal{S}$.

Note that by picking appropriate $d$ and $t$, theorem 1 yields a polynomial-time algorithm for MWIS for bounded-degree graphs excluding a fixed graph from $\mathcal{S}$ as an induced subgraph.

Then we proceed to the main result of the paper: we show that MWIS remains polynomial-time solvable in $dS_{t,t,t}$-free graphs, even if instead of bounding the maximum degree, we forbid a fixed biclique as a subgraph.

Let us remark that by the celebrated Kövári-Sós-Turán theorem [33], classes that exclude $K_{s,s}$ as a subgraph capture all hereditary classes of sparse graphs, where by “sparse” we mean that the graph has a subquadratic number of edges. Furthermore, by a simple Ramsey argument, for every positive integer $r$ there exists an integer $s$ such that if $G$ is $K_{r}$-free and $K_{r,r}$-free then $G$ does not contain $K_{s,s}$ as a subgraph. Hence, equivalently, theorem 2 yields a polynomial-time algorithm for MWIS for graphs that are simultaneously $H$-free (for some $H\in\mathcal{S}$), $K_{r}$-free, and $K_{r,r}$-free.

As in the previous works [16, 24], the crucial tool in handling $dS_{t,t,t}$-free graphs is an extended strip decomposition. Its technical definition can be found in preliminaries; for now, it suffices to say that it is a wide generalization of the preimage graph of a line graph (recall that line graphs are $S_{1,1,1}$-free) that allows for recursion for the MWIS problem. An extended strip decomposition of a graph $G$ identifies some induced subgraphs of $G$ as particles and, knowing the maximum possible weight of an independent set in each particle, one can compute in polynomial time the maximum possible weight of an independent set in $G$. (We remark that this computation involves advanced combinatorial techniques as it relies on a reduction to the maximum weight matching problem in an auxiliary graph.) In other words, finding an extended strip decomposition with small particles compared to $|V(G)|$ is equally good for the MWIS problem as splitting the graph into small connected components.

The starting point is the following theorem of [42].

(A rigid extended strip decomposition is an extended strip decomposition that does not have some unnecessary empty sets. By $N[X]$ we denote the set consisting of $X$ and all vertices with a neighbor in $X$.) Let us remark that the result stated in [42, Theorem 2] is for unweighted graphs (i.e., $U=V(G)$ using the notation from theorem 3), but the statement of theorem 3 can be easily derived from the proof, see also [24].

Consider the setting of theorem 1, i.e., the graph $G$ has maximum degree $\Delta$. Apply theorem 3 to $G$ with $U=V(G)$. If we get the first outcome, i.e., an induced $dS_{t,t,t}$ in $G$, we return it and terminate. So assume that we get the second outcome, i.e., the set $X$. Note that as $|X|=\mathcal{O}(dt+t\log n)$, we have $|N[X]|=\mathcal{O}(dt\Delta+t\Delta\log n)$. It is now tempting to exhaustively branch on $N[X]$ (i.e., guess the intersection of the sought independent set with $N[X]$) and recurse on the particles of the extended strip decomposition of $G-N[X]$. However, implementing this strategy directly gives quasipolynomial (in $n$) running time bound of $n^{\mathcal{O}(dt\Delta+t\Delta\log n)}$, as the branching step yields up to $2^{|N[X]|}=2^{\mathcal{O}(dt\Delta)}\cdot n^{\mathcal{O}(t\Delta)}$ subcases and the depth of the recursion is $\mathcal{O}(\log n)$.

Our main new idea now is to perform this branching lazily, by considering a more general border version of the problem, where the input graph is additionally equipped with a set of terminals and we ask for a maximum weight of an independent set for every possible behavior on the terminals.

A similar application of a border version of the problem to postpone branching in recursion appeared for example in the technique of recursive understanding [31, 14].

Let us return to our setting, where we have a set $X$ of size $\mathcal{O}(dt+t\log n)$ and an extended strip decomposition of $G-N[X]$ with particles of size at most half of the size of $V(G)$. We would like to remove $N[X]$ from the graph, indicate $N(N[X])$ as terminals and solve Border MWIS in $(G-N[X],\mathbf{w},T:=N(N[X]))$ using the extended strip decomposition for recursion. Note that, thanks to the bounded degree assumption, the size of $T=N(N[X])$ is bounded by $\mathcal{O}(dt\Delta^{2}+t\Delta^{2}\log n)$.

This approach almost works: the only problem is that, as the recursion progresses, the set of terminals accummulates and its size can grow beyond the initial $\mathcal{O}(dt\Delta^{2}+t\Delta^{2}\log n)$ bound. Luckily, this can be remedied in a standard way: we alternate recursive steps where theorem 3 is invoked with $U=V(G)$ with steps where theorem 3 is invoked with $U=T$. In this manner, we can maintain a bound of $\mathcal{O}(dt\Delta^{2}+t\Delta^{2}\log n)$ on the number of terminals in every recursive call. Note that this bound also guarantees that the size of the domain of the requested function $f_{G,\mathbf{w},T}$ is of size $2^{\mathcal{O}(dt\Delta^{2})}n^{\mathcal{O}(t\Delta^{2})}$, which is within the promised time bound.

Let us now move to the more general setting of theorem 2. Here, the starting points are the recent results of Weißauer [52] and Lozin and Razgon [40] that show that in the $S_{t,t,t}$-free case, excluding a biclique as a subgraph is not that much different than bounding the maximum degree.

A $k$-block in a graph is a set of $k$ vertices, no two of which can be separated by deleting fewer than $k$ vertices. The following result was shown by Weißauer (we refer to preliminaries for standard definitions of tree decompositions and torsos).

Even though the statement of the result in [52] is just existential, the proof actually yields a polynomial-time algorithm to compute such a tree decomposition.

It turns out that $dS_{t,t,t}$-free graphs with no large bicliques have no large blocks.

Let us remark that Lozin and Razgon [40] showed lemma 5 for $S_{t,t,t}$-free graphs. However, an extension of their argument applies to $dS_{t,t,t}$-free graphs; we include it in Appendix A.

Combining theorem 4 and lemma 5 we immediately obtain the following.

To prove theorem 2 using corollary 6 we need to carefully combine explicit branching on the (bounded number of) vertices of large degree in a single bag with — as in the bounded degree case — applying theorem 3 to the remainder of the graph and indicating $N(N[X])$ as the terminal set of the border problem passed to the recursive calls. Finally, we combine these steps with the information passed over adhesions in the tree decomposition.