Independent Set on P_k-Free Graphs in Quasi-Polynomial Time

An independent set (also known as a stable set) in a graph $G$ is a vertex set $S$ such that no pair of distinct vertices in $S$ are adjacent in $G$. In the Independent Set problem the input is a graph $G$ on $n$ vertices and integer $k$, the task is to determine whether $G$ contains an independent set $S$ of size at least $k$. Independent Set is a well-studied and fundamental graph problem which is NP-complete [GJ79a, Kar72] and intractable within most frameworks for coping with NP-hardness. Indeed, Independent Set was one of the very first problems to be shown to be NP-hard to approximate [FGLaMS96, Zuc07], one of the first intractable problems from the perspective of parameterized complexity [DF99], one of the first problems to be shown not to have a $2^{o(n)}$ time algorithm assuming the Exponential Time Hypothesis (ETH) [IPZ01], and one of the very first problems whose hardness of parameterized approximation, assuming the Gap-ETH, was established [CCK⁺17].

With the above in mind, it is natural that a significant research effort has been devoted to identifying classes of input graphs for which the Independent Set problem is substantially easier than on general graphs. Of particular interest are the classes where Independent Set becomes polynomial time solvable. Most famously the problem becomes polynomial time solvable on Perfect graphs [GLS81], other examples of polynomial time solvable cases include $k\times K_{2}$-free graphs [BY89] and graphs of bounded cliquewidth [CMR00]. For an extensive list, see [BS⁺99] and the companion website [DR⁺16]. On the other hand the problem remains NP-complete even on planar graphs of maximum degree 3 [GJ79b], unit disc graphs [CCJ90], triangle-free graphs [Pol74] and AT-free graphs [BKKM99].

This paper fits in a long line of work to precisely classify the complexity of Independent Set on all hereditary graph classes defined by a single forbidden induced subgraph $H$ (and more generally, by a finite set ${\cal H}$ of forbidden induced subgraphs). A graph $G$ is said to be $H$-free if $G$ does not contain a copy of $H$ as an induced subgraph. For a set ${\cal H}$ of graphs, $G$ is ${\cal H}$-free if $G$ is $H$-free for all $H\in{\cal H}$. The ultimate goal of this research direction is to establish a dichotomy theorem that for every finite set ${\cal H}$ of graphs determines whether Independent Set on ${\cal H}$-free graphs is polynomial time solvable, or NP-complete¹¹1There is of course the possibility that Independent Set on ${\cal H}$-free graphs has NP-intermediate complexity for some choice of ${\cal H}$. We believe this is unlikely, however that is pure speculation..

In 1982 Alekseev [Ale82] observed that Independent Set remains NP-complete on the class of ${\cal H}$-free graphs for every finite set ${\cal H}$ that does not include a graph $H$ whose every connected component is a path or a subdivision of the claw ($K_{1,3}$). Since then, no new NP-completeness results for Independent Set on ${\cal H}$-free graphs have been found for any other finite set ${\cal H}$. Thus, it is consistent with current knowledge that Independent Set is polynomial time solvable on ${\cal H}$-free graphs for all other finite sets ${\cal H}$. At the same time, progress on algorithms has been embarrassingly slow. The only connected graphs $H$ for which NP-completness of Independent Set does not follow from Alekseev’s result are paths and subdivisions of the claw. Polynomial time algorithms for Independent Set on claw-free graphs were found independently by Sbihi [Sbi80] and Minty [Min80] in 1980. A polynomial time algorithm on fork-free graphs (a fork is a claw with one subdivided edge) was found by Alekseev [Ale04]. Subsequently, Lozin and Milanic [LM08] gave an algorithm for Weighted Independent Set on fork-free graphs. For paths, Independent Set on $P_{4}$-free graphs was shown to be polynomial time solvable by Corneil et al. [CLB81] in 1981. After a series of papers giving polynomial time algorithms for various subclasses of $P_{5}$-free graphs [BL03, BM03, GL03, LM05, Mos08, RS10], in 2014 Lokshtanov et al. [LVV14] gave a polynomial time algorithm on $P_{5}$ free graphs. Two years later, Lokshtanov et al. [LPvL18] devised a quasi-polynomial time algorithm on $P_{6}$-free graphs, before Grzesik et al. [GKPP19] designed a polynomial time algorithm for $P_{6}$-free graphs in 2019. This summarizes the state-of-the-art for polynomial time solvability of Independent Set on $H$-free graphs.

It appears that the currently known techniques are very far from being able to yield polynomial time algorithms for Independent Set on $P_{k}$-free graphs for $k=8$, let alone for all values of $k$. More concretely, the polynomial time algorithms for $P_{5}$-free graphs of Lokshtanov et al. [LVV14] and for $P_{6}$-free graphs of Grzesik et al. [GKPP19] are based on the same method. First, from a sample of two articles the complexity of applying this method seems to grow exponentially with $k$. Second, and more importantly, in a recent manuscript Grzesik et al. [GKPP20] show that a crucial component of this method fails completely on $P_{k}$-free graphs for $k\geq 8$.

The slow progress on polynomial time algorithms have prompted researchers to look for weaker forms of tractability of Independent Set on $P_{k}$-free graphs. Bacsó et al. [BLM⁺19] provided $2^{O(\sqrt{kn\log n})}$ time algorithms for Independent Set on $P_{k}$-free graphs (see also [Bra17, GOR⁺19]). Finally, Chudnovsky et al. [CPPT20] obtained quasi-polynomial time approximation schemes for $P_{k}$-free graphs for all $k$. In fact their result is much more general - they obtain quasi-polynomial time approximation schemes on ${\cal H}$-free graphs for all sets ${\cal H}$ for which NP-hardness does not follow from Alekseev’s [Ale82] observation. While the results above are general, they are consistent with Independent Set being NP-complete on all ${\cal H}$-free classes of graphs on which polynomial time algorithms are not already known. In this paper we obtain a quasi-polynomial time algorithm for Weighted Independent Set on $P_{k}$-free graphs for every $k$. In particular we prove the following theorem.

Theorem 1 implies that unless ${\sf NP}\subseteq{\sf QP}$, Independent Set on $P_{k}$-free graphs is not NP-complete for any $k$. This is the first conclusive evidence against NP-completeness for any $k\geq 7$. The running time of the algorithm of Theorem 1 matches that of Chudnovsky et al. [CPPT20], but computes optimal solutions instead of $(1-\epsilon)$-approximate ones. It is also worth mentioning that our algorithm and analysis is substantially simpler than the quasi-polynomial time algorithm of Lokshtanov et al. [LPvL18] for the special case of $P_{6}$-free graphs. We have been unsuccessful in generalizing Theorem 1 to a quasi-polynomial time algorithms for $H$-free graphs where $H$ is a subdivision of a claw. However, the techniques used to prove Theorem 1 can be used to show that such an algorithm would automatically generalize to all classes of ${\cal H}$-free graphs for which NP-hardness is not already known. More concretely, for a graph $H$ let O_H be an oracle that takes as input an $H$-free graph $G$ and outputs the weight of a maximum weight independent set in $G$. Further, let ${\cal CC}(H)$ denote the set of connected components of $H$. Our second result is the following.

Theorem 2 has two immediate consequences. First, coupled with Theorem 1 and the polynomial time algorithm for Weighted Independent Set on fork-free graphs, Theorem 2 yields a quasi-polynomial time algorithm for Weighted Independent Set on $T_{k}$-free graphs, where $T_{k}$ is the graph with $k$ connected components the first of which is a $P_{k}$ and each of the remaining $k-1$ are isomorphic to a fork. Second, Theorem 2 implies that if Weighted Independent Set has a quasi-polynomial time algorithm on $H$-free graphs for every subdivided claw $H$, then Weighted Independent Set also has a quasi-polynomial time algorithm on all ${\cal H}$-free classes of graphs, for finite sets ${\cal H}$, for which NP-hardness does not follow from Alekseev’s result. Or, stated more poetically, the buck stops at the (subdivided) claw.

All graphs in this paper are assumed to be simple, undirected graphs. We denote the edge set of a graph $G$ by $E(G)$ and the vertex set of a graph by $V(G)$. If $v$ $\in$ $V(G)$, then we use $N[v]$ to denote the closed neighborhood of v, i.e. the set of all neighbors of $v$ together with $v$ itself. We use $N(v)$ to denote the set $N[v]-\{v$}. If $X$ $\subseteq$ $V(G)$, then $N[X]$ = $\bigcup_{x\in X}N[x]$ and $N(X)$ = $N[X]-X$. We use ${\cal CC}(G)$ to denote the set of connected components of $G$. If $G_{1}$, $G_{2}$,…, $G_{m}$ are graphs, then we use $G_{1}+G_{2}+...+G_{m}$ to denote the graph that that has vertex set $V(G_{1})\cup V(G_{2})\cup...\cup V(G_{m})$, and edge set $E(G_{1})\cup E(G_{2})\cup...\cup E(G_{m})$.

Given a weight function $w:V(G)\rightarrow\mathbb{N}$ the weight of a vertex set $S$ is defined as $w(S)=\sum_{v\in S}w(v)$. An independent set in $G$ is a vertex set $S$ such that no pair of vertices in $S$ have an edge between them. We define mwis$(G)$ to be the weight of the maximum weight independent set in $G$. The $length$ of a path is the number of vertices in the path and we denote by $P_{k}$ the path of length $k$. If $X$ $\subseteq$ $V(G)$ then we will use $G(X)$ to denote the the graph induced by the vertex set $X$, and if it is clear from the context we will use $G-X$ to denote the graph $G(V(G)-X)$.

Given a positive number $k$ and a graph $G$, we call a set $S$ $\subset$ $V(G)$ a $c$-$balanced$ $separator$ if no connected component of $G-S$ has over $c$ vertices. A vertex multi-family ${\cal F}$ is a collection of vertex sets that allows for multiple instances of its vertex sets. If ${\cal F}$ = {$S_{1},S_{2},\ldots,S_{n}\}$ and $X$ is a set of vertices, then ${\cal F}-X$ is the vertex multi-family {$S_{1}-X,S_{2}-X,\ldots,S_{n}-X\}$. For two vertex multi-families ${\cal A}$ and ${\cal B}$ their union is denoted by ${\cal A}\cup{\cal B}$ and is defined by the vertex multi-family that contains all elements of ${\cal A}$ and of ${\cal B}$. The multiplicity of an element $X$ in ${\cal A}\cup{\cal B}$ is its multiplicity in ${\cal A}$ plus its multiplicity in ${\cal B}$. We will use $\log(x)$ to denote the function $\lceil\log_{2}(x)\rceil$ throughout this paper.

In this section we prove Theorem 1. We will make use of the following balanced separator lemma from Basco et al. [BLM⁺19].

We begin by proving a slight strengthening of Lemma 1.

To describe the algorithm of Theorem 1 we first need to define the notion of level sets relative to a vertex multi-family ${\cal F}$.

In other words $L({\cal F},i)$ is a vertex set containing all vertices of $G$ that are contained in at least $i$ sets in ${\cal F}$. Our algorithm will also make use of a number $N$, this number will be approximately equal to the number of vertices in the input graph $G$.

In the following $G$ is always a graph, $w$ is a weight function $w:V(G)\rightarrow\mathbb{N}$, $N$ is an integer, and ${\cal F}$ is a multi-family of subsets of $V(G)$. We now describe the main subroutine ALG₁ in the algorithm of Theorem 1. The algorithm takes as input $G$, $w$, $N$ and ${\cal F}$ and (as we will prove) outputs the weight of a maximum weight independent set in $G$. The algorithm of Theorem 1 will call ALG₁ with parameters G, $N=|V(G)|$, w, and ${\cal F}=\emptyset$. ALG₁ is a recursive branching algorithm with only four rules. First, if $G$ has at most one vertex, then return $V(G)$. Second, if the largest component of $G$ has at most $|N|/2$ vertices then solve the problem recursively on each component and return the sum. Third, if there exists a branchable vertex $v$, then branch on $v$ (i.e solve the problem with $v$ forced in to the independent set, and $v$ forced out). Finally, if none of the previous rules apply then add a new balanced separator $X$ (obtained by Lemma 2) to ${\cal F}$. In other words, make a recursive call on the instance $(G,w,N,{\cal F}\cup\{N[X]\})$.

ALG₁ is very similar to well known exact exponential time branching algorithms for Independent Set [FK10]. The key differences are that we use the multi-family ${\cal F}$ of balanced separators to guide which vertex to branch on, that when no rules apply we add a separator to the family ${\cal F}$ (at a glance this appears to make no progress at all, but it increases the size of the level sets, making more vertices branchable), and that we wait with recursing on connected components until the size of the largest component becomes less than $N/2$ (this is primarily to simplify the analysis).

We will distinguish between the three different kinds of recursive calls that ALG₁ can make. If the else if condition on line 5 holds, then the algorithm makes the recursive calls on line 6. In this case we say that ALG₁ recurses on connected components. If the else if condition on line 7 holds, then the algorithm makes the recursive calls on line 8. In this case we say that ALG₁ branches on a branchable vertex. Otherwise the algorithm makes the recursive call on line 10. In this case we say that ALG₁ adds a balanced separator. We will frequently need to refer to parts of the execution of the algorithm. For disambiguation, we collect the terminology here.

An instance is a four-tuple $(G,w,N,{\cal F})$. A run of the algorithm refers to the entire execution of the algorithm on an instance. A call $\mbox{ALG}_{1}(G,w,N,{\cal F})$ refers to the computation done in the root node of the recursion tree of the run $\mbox{ALG}_{1}(G,w,N,{\cal F})$. We remark that parameters $G,w,N$, and ${\cal F}$ never change during the call $\mbox{ALG}_{1}$($G,w,N,{\cal F})$. When a run or a call ALG${}_{1}(G,w,N,{\cal F})$ recursively calls ALG₁ on the instance $(G^{\prime},w,N^{\prime},{\cal F}^{\prime})$ we say the run or the call executes a run or a call on $(G^{\prime},w,N^{\prime},{\cal F}^{\prime})$. This will sometimes be referred to as makes a recursive call $\mbox{ALG}_{1}(G^{\prime},w,N^{\prime},{\cal F}^{\prime})$. A run of $\mbox{ALG}_{1}(G,w,N,{\cal F})$ is called a $k$-$fair$ $run$ if $G$ is a $P_{k}$-free graph, $N=|V(G)|$, ${\cal F}=\emptyset$, and $w$ is a weight function. A call $\mbox{ALG}_{1}(G,w,N,{\cal F})$ is called a $k$-$fair$ $call$ if it is executed during the course of a $k$-fair run. An instance $(G,w,N,{\cal F})$ is called a $k$-fair instance if $\mbox{ALG}_{1}(G,w,N,{\cal F})$ is a k-fair call.

We have now proved that ALG₁ always terminates and that it always outputs the correct answer. The remainder of the section is devoted to the running time analysis. We will now prove some lemmas to help us bound the run time of ALG₁ on $k$-fair runs. First, in Observation 1 we will prove that ${\cal F}$ remains a multi-family of balanced separators of $G$ throughout the execution of the algorithm. In Observation 2 we will show that no vertex appears in many (more than $\log N$) sets in ${\cal F}$. This will ensure that ${\cal F}$ can never grow too large, because, as we will show in Lemma 5, a connected $P_{k}$-free graph can not contain a large fractional packing of balanced separators.

The following observation shows that the level sets do not grow a lot in each successive recursive call, and that they therefore never get very large. Note in particular that the size of level set $i$ drops exponentially with $i$.

For $k$-fair instances $(G,w,N,{\cal F})$ we define a measure:

If $(G,w,N,{\cal F})$ is not a $k$-fair instance, then $\mu_{k}(G,w,N,{\cal F})$ is undefined. Note that $\mu_{k}(G,w,N,{\cal F})$ must always be an integer, and that it is independent of the weight function $w$. We will say that two instances $(G,w,N,{\cal F})$ and $(G^{\prime},w^{\prime},N^{\prime},{\cal F}^{\prime})$ are essentially different if $G^{\prime}\neq G$, $N^{\prime}\neq N$ or ${\cal F}^{\prime}\neq{\cal F}$.