Exact Algorithms for Maximum Weighted Independent Set on Sparse Graphs (Extended Abstract)

Abstract

The maximum independent set problem is one of the most important problems in graph algorithms and has been extensively studied in the line of research on the worst-case analysis of exact algorithms for NP-hard problems. In the weighted version, each vertex in the graph is associated with a weight and we are going to find an independent set of maximum total vertex weight. In this paper, we design several reduction rules and a fast exact algorithm for the maximum weighted independent set problem, and use the measure-and-conquer technique to analyze the running time bound of the algorithm. Our algorithm works on general weighted graphs and it has a good running time bound on sparse graphs. If the graph has an average degree at most 3, our algorithm runs in $O^*(1.1443^n)$ time and polynomial space, improving previous running time bounds for the problem in cubic graphs using polynomial space.

The work is supported by the National Natural Science Foundation of China, under grant 61972070.

1 Introduction

The Maximum Independent Set problem on unweighted graphs belongs to the first batch of 21 NP-hard problems proved by Karp [12]. In the line of research on the worst-case analysis of exact algorithms for NP-hard problems, Maximum Independent Set, as one of the most fundamental problems, is used to test the efficiency of new techniques of exact algorithms. There is a long list of contributions to exact algorithms for Maximum Independent Set in unweighted graphs [2, 8, 11, 13, 16, 17]. Now it can be solved in $O^*(1.1996^n)$ time and polynomial space [21]. If the maximum degree of the graph is 3, the running time bound can be improved to $O^*(1.0836^n)$ [20].

In this paper, we will consider the weighted version of Maximum Independent Set, called Maximum Weighted Independent Set, where each vertex in the graph has a nonnegative weight and we are asked to find an independent set with the maximum total vertex weight. It has many applications in various real-world problems. For example, the dynamic map labeling problem [1, 15] can be naturally encoded as Maximum Weighted Independent Set. Some experimental algorithms, such as the algorithms in [14, 19] have been developed to solve instances from real world and known benchmarks. These algorithms run fast even on large scale sparse instances but lack running time analysis. For running time bounds, most known results were obtained via two counting problems: Counting Maximum Weighted Independent Set and Counting Weighted 2-SAT. Most of these counting algorithms can also list out all independent sets and then we can find a maximum one by increasing only a polynomial factor. Dahllöf et al. [4] presented an $O^*(1.3247^n)$-time algorithm for Counting Maximum Weighted Independent Set. Later, the running time bound was improved to $O^*(1.2431^n)$ by Fomin et al. [6]. Counting Maximum Weighted Independent Set can also be reduced to Counting Weighted 2-SAT, preserving the exponential part of the running time. For Counting Weighted 2-SAT, the running time bound was improved from $O^*(1.2561^n)$ [5] to $O^*(1.2461^n)$ [9] and then to $O^*(1.2377^n)$ [18]. Wahlström [18] also showed that the running time bound could be further improved to $O^*(1.1499^n)$ and $O^*(1.2117^n)$ if the maximum degree of the variables or the vertices in the graph is bounded by 3 and 4, respectively. Most of the above algorithms use only polynomial space. If exponential space is allowed, dynamic programming algorithms based on tree decompositions, by using the treewidth bound on degree-3 graphs in [7], may achieve a better running time bound $O^*(1.1225^n)$.

In this paper, we will focus on exact algorithms specifying for Maximum Weighted Independent Set. We develop structural properties and design reduction rules for the problem, and then design a fast exact algorithm based on them. By using the measure-and-conquer technique, we can prove that the algorithm runs in $O^*(1.1443^{(0.624x-0.872)n})$ time and polynomial space, where x is the average degree of the graph. For some sparse graphs, our result beats the known bounds. For example, the running time bound of our algorithm in graphs with the average degree at most three is $O^*(1.1443^n)$, which improves the previously known bound of $O^*(1.1499^n)$ using polynomial space [18]. For graphs with the average degree at most 3.68, the running time of our algorithm is strictly better than the running time bound $O^*(1.2117^n)$ for Maximum Weighted Independent Set in degree-4 graphs [18].

Due to the limited space, the proofs of lemmas marked with (*) were omitted, which can be found in the full version of this paper [10].

2 Preliminaries

Let $G=(V,E,w)$ denote an undirected vertex-weighted graph with $|V|=n$ vertices and $|E|=m$ edges, where each vertex $v\in V$ is associated with a positive weight w(v). Although our graphs are undirected, we may use an arc to denote the relation of the weights of the two endpoints of an edge. An arc $\overrightarrow{uv}$ from vertex u to vertex v means that there is an edge between u and v and it holds that $w(u)\ge w(v)$.

Let $V'\subseteq V$ be a vertex subset. We let $w(V')=\sum _{v\in V'}w(v)$, and $N(V')$ denote the set of vertices not in $V'$ but adjacent to at least one vertex in $V'$. We also denote $d(V')=|N(V')|$ and $N[V']=N(V')\cup V'$. We use $G[V']$ to denote the subgraph of G induced by $V'$ and use $G-V'$ to denote $G[V\setminus V']$. For a graph $G'$, we use $\mathcal {C}(G')$ to denote the set of connected components of $G'$. A chain is an induced path such that the degree of each vertex except the two endpoints of the path is exactly 2. One vertex is a chain-neighbor of another vertex if they are connected by a chain. For a vertex-weighted graph, a maximum weighted independent set is an independent set S such that w(S) is maximized among all independent sets in the graph. We use S(G) to denote a maximum weighted independent set in graph G and $\alpha (G)$ to denote the total vertex weight of S(G). Our problem is defined below.

2.1 Measure-and-Conquer

Our algorithm is a branch-and-search algorithm. We will use a measure to evaluate the time complexity. For a branching operation, if the measure decreases by at least $a_i$ in the i-th substance, then we say the branching vector of the operation is $[a_1,a_2,\dots ,a_l]$. The largest root of the function $f(x) = 1-\sum _{i=1}^lx^{-a_i}$ is called the branching factor of the recurrence.

The measure-and-conquer technique, introduced in [8], is a powerful tool to analyze branch-and-search algorithms. The main idea is to use a non-traditional measure to evaluate the running time. Let $n_i$ denote the number of vertices of degree i in the graph. We associate a cost $\delta _i\ge 0$ for each degree-i vertex in the graph. Our measure p is defined as follows:

$$\begin{aligned} p:=\sum _{i=0}^nn_i\delta _i. \end{aligned}$$

(1)

The cost $\delta _i$ in this paper is given by

$$\begin{aligned} \delta _i \mathrm{{ = }}\left\{ {\begin{array}{*{20}{l}} 0&{}{\mathrm{{if}} ~i \le 1}\\ {0.376}&{}{\mathrm{{if}} ~i=2}\\ 1&{}{\mathrm{{if}} ~i=3}\\ {1+0.624(i-3)}&{}\mathrm{{if}} ~i \ge 4. \end{array}} \right. \end{aligned}$$

(2)

We also define $\delta _i^{<-k>}:=\delta _i-\delta _{i-k}$ for each integer $k\ge 0$. In our analysis, we may use the following inequalities and equalities to simplify some arguments: $\delta _i^{<-1>}=\delta _3^{<-1>}$ for $i\ge 4$; $\delta _3\ge 2.5\delta _2; 3\delta _2\ge \delta _3$.

With the above setting, we know that when $p\le 0$, the instance contains only degree-0 and degree-1 vertices and can be solved directly. We will design an algorithm with running time bound $O^*(c^p)$ for some constant c. If the initial graph has degree at most 3, then we have that $p\le n$ and then the running time bound of the algorithm is $O^*(c^n)$. In general, if we have $p\le f(n)$ for some function f on n, then we can get a running time bound of $O^*(c^{f(n)})$. We have the following lemma for the relation between p and n.

Lemma 1

(*) For a graph of n vertices, if the average degree of the graph is at most x, then the measure p of the graph is at most $(0.624x-0.872)n$.

3 Reduction Rules

We first introduce reduction rules that will be applied to reduce the instance directly by eliminating some local structures of the graph. Some reduction rules may include a set S of vertices in the solution set directly. We use $M_c$ to store the weight of the vertices that have been included in the solution set. When a set S of vertices is included in the solution set, we will remove N[S] from the graph and update $M_c$ by adding w(S).

3.1 General Reductions for Some Special Structures

We use several reduction rules based on unconfined vertices, twins, vertices with a clique neighborhood, and heavy vertices. Some of these reduction rules were introduced in [14] and [19].

Unconfined Vertices. A vertex v in G is called removable if $\alpha (G)=\alpha (G-v)$, i.e., there is a maximum weighted independent set in G that does not contain v. We can say that a vertex v is removable if a contradiction is obtained from the assumption that every maximum weighted independent set in G contains v. A sufficient condition for a vertex to be removable in unweighted graphs has been studied in [20]. We extend this concept to weighted graphs.

For an independent set S of G, a vertex $u\in N(S)$ is called a child of S if $w(u)\ge w(S\cap N(u))$. A child u is called an extending child if it holds that $|N(u)\setminus N[S]|=1$, and the only vertex $v\in N(u)\setminus N[S]$ is called a satellite of S.

Lemma 2

(*) Let S be an independent set that is contained in any maximum weighted independent set in G. Then every maximum weighted independent set contains at least one vertex in $N(u)\setminus N[S]$ for each child u of S.

We introduce a method based on Lemma 2 to find possible removable vertices. Let v be an arbitrary vertex in the graph. After starting with $S:=\{v\}$, we repeat (1) until (2) or (3) holds:

• (1) If S has some extending child in N(S), then let $S'$ be the set of satellites. Update S by letting $S:=S\cup S'$.

• (2) If S is not an independent set or there is a child u such that $N(u)\setminus N[S]=\emptyset$, then halt and conclude that v is unconfined.

• (3) If $|N(u)\setminus N[S]|\ge 2$ for all children $u\in N(S)$, then halt and return $S_v=S$.

Obviously, the procedure can be executed in polynomial time for any starting set S of a vertex. If the procedure halts in (2), we say vertex v unconfined. If the procedure halts in (3), then we say that the set $S_v$ returned in (3) confines vertex v and vertex v is also called confined. Note that the set $S_v$ confining v is uniquely determined by the procedure with starting set $S:=\{v\}$. It is easy to observe the following lemma.

Lemma 3

(*) Any unconfined vertex is removable.

Reduction Rule 1

(R1). If a vertex v is unconfined, remove v from G.

Twins. A set $A=\{u,v\}$ of two non-adjacent vertices is called a twin if they have the same neighbor set, i.e., $N(u)=N(v)$.

Reduction Rule 2

(R2) [14]. If there is a twin $A=\{u,v\}$, delete v and update the weight of u by letting $w(u):=w(u)+w(v)$.

Clique Neighborhood. A vertex v has a clique neighborhood if the graph G[N(v)] induced by the open neighbor set of v is a clique, which was introduced as isolated vertices in [14].

Reduction Rule 3

(R3) [14]. If there is a vertex v having a clique neighborhood and $w(v)<w(u)$ holds for all $u\in N(v)$, then remove v from the graph, update the weight $w(u):=w(u)-w(v)$ for all $u\in N_G(v)$, and add w(v) to $M_c$.

Heavy Vertices. A vertex v is called a heavy vertex if its weight is not less the weight of the maximum weighted independent set in subgraph induced by the open neighborhood of it, i.e., $w(v)\ge \alpha (G[N(v)]).$

Reduction Rule 4

(R4). If there is a heavy vertex v of degree at most 5, then delete N[v] from the graph and add w(v) to $M_c$.

It is an effective rule that has been used in some experimental algorithms [14, 19]. In this paper, we will only check heavy vertices of degree bounded by 5 and then it can be done in polynomial time. Note that degree-0 vertices will be reduced as heavy vertices in this step.

3.2 Reductions Based on Degree-2 Vertices

For unweighted graphs, we have good reduction rules to deal with all degree-2 vertices (see the reduction rule in [3]). However, for weighted graphs, it becomes much more complicated. The following R5 is generalized from the concept of folding degree-2 vertices in unweighted graphs in [3], which has been also used in some experimental algorithms [14, 19]. We also consider more reduction rules for degree-2 vertices in some complicated structures.

Reduction Rule 5

(R5). If there is a degree-2 vertex v with two neighbors $\{u_1,u_2\}$ such that $w(u_1)+w(u_2)>w(v)\ge max\{w(u_1),w(u_2)\}$, then delete $\{v, u_1,u_2\}$ from the graph G, introduce a new vertex $v'$ adjacent to $N_G(\{v,u_1,u_2\})$ with weight $w(v'):=w(u_1)+w(u_2)-w(v)$, and add w(v) to $M_c$.

Reduction Rule 6

(R6) ([19]). If there is a path $v_1v_2v_3v_4$ such that $d_G(v_2)=d_G(v_3)=2$ and $w(v_1)\ge w(v_2)\ge w(v_3)\ge w(v_4)$, then remove $v_2$ and $v_3$ from the graph, add an edge $v_1v_4$ if it does not exist, update the weight of $v_1$ by letting $w(v_1):=w(v_1)+w(v_3)-w(v_2)$, and add $w(v_2)$ to $M_c$.

Reduction Rule 7

(R7) ([19]). If there is a 4-cycle $v_1v_2v_3v_4$ such that $d_G(v_2)=d_G(v_3)=2$ and $w(v_1)\ge w(v_2)\ge w(v_3)$, then remove $v_2$ and $v_3$, update the weight of $v_1$ by letting $w(v_1):=w(v_1)+w(v_3)-w(v_2)$, and add $w(v_2)$ to $M_c$.

Reduction Rule 8

(R8). If there is a 4-path $v_1v_2v_3v_4v_5$ such that $d_G(v_2)=d_G(v_3)=d_G(v_4)=2$ and $w(v_1)\ge w(v_2)\ge w(v_3)\le w(v_4)\le w(v_5)$, then remove $v_2$ and $v_4$, add edges $v_1v_3$ and $v_3v_5$, update the weight of $v_1$ by letting $w(v_1):=w(v_1)+w(v_3)-w(v_2)$ and the weight of $v_5$ by letting $w(v_5):=w(v_5)+w(v_3)-w(v_4)$, and add $w(v_2)+w(v_4)-w(v_3)$ to $M_c$.

Reduction Rule 9

(R9). For a 5-cycle $v_1v_2v_3v_4v_5$ such that $d_G(v_2)=d_G(v_3)=d_G(v_5)=2$, $\min \{d(v_1),d(v_4)\}\ge 3$, and $w(v_1)\ge w(v_2)\ge w(v_3)\le w(v_4)$,

• (1) if $w(v_3)>w(v_5)$, then remove $v_5$, update the weight of $v_i$ by letting $w(v_i):=w(v_i)-w(v_5)$ for $i=1,2,3,4$, and add $2w(v_5)$ to $M_c$.

• (2) if $w(v_3)\le w(v_5)$, then remove $v_2$ and $v_3$, update the weight of $v_1$ by letting $w(v_1):=w(v_1)-w(v_2)$, the weight of $v_4$ by letting $w(v_4):=w(v_4)-w(v_3)$ and the weight of $v_5$ by letting $w(v_5):=w(v_5)-w(v_3)$, and add $w(v_2)+w(v_3)$ to $M_c$.

Reduction Rule 10

(R10). For a 6-cycle $v_1v_2v_3v_4v_5v_6$ such that $d_G(v_2)=d_G(v_3)=d_G(v_5)=d_G(v_6)=2$, $w(v_1)\ge \max \{w(v_2),w(v_6)\}$, $w(v_4)\ge \max \{w(v_3),w(v_5)\}$, and $w(v_6)\ge w(v_5)$,

• (1) if $w(v_2)\ge w(v_3)$, then remove $v_5$ and $v_6$, and update the weight of $v_2$ by letting $w(v_2):=w(v_2)+w(v_6)$ and the weight of $v_3$ by letting $w(v_3):=w(v_3)+w(v_5)$;

• (2) if $w(v_2)< w(v_3)$, then remove $v_6$, add edge $v_1v_5$, and update the weight of $v_2$ by letting $w(v_2):=w(v_2)+w(v_6)$, the weight of $v_3$ by letting $w(v_3):=w(v_3)+w(v_5)$, and the weight of $v_5$ by letting $w(v_5):=w(v_6)+w(v_3)-\max \{w(v_2)+w(v_6),w(v_3)+w(v_5)\}$.

3.3 Reductions Based on Small Cuts

We also have some reduction rules to deal with vertex-cuts of size one or two, which can even be used to design a polynomial-time divide-and-conquer algorithm. However, a graph may not always have vertex-cuts of small size.

Reduction Rule 11

(R11). For a vertex-cut $\{u\}$ with a connected component $G^*$ in $G-u$ such that $2\delta _3-\delta _2\le \sum _{v\in G^*}\delta _{d_G(v)} \le 10$,

• (1) if $w(u)+\alpha (G^*- N[u])\le \alpha (G^*)$, then remove $G^*$ and $\{u\}$ from G and add $\alpha (G^*)$ to $M_c$;

• (2) if $w(u)+\alpha (G^*- N[u])> \alpha (G^*)$, then remove $G^*$ from G, update the weight of u by letting $w(u):=w(u)+\alpha (G^*- N[u])-\alpha (G^*)$, and add $\alpha (G^*)$ to $M_c$.

Lemma 4

(*) Let $\{u, u'\}$ be a vertex-cut of size two in G and $G^*$ be a connected component in $G-\{u,u'\}$, where we assume w.l.o.g. that $\alpha (G^*-N[u])\ge \alpha (G^*-N[u'])$. We construct a new graph $G'$ from G as follows: remove $G^*$; add three new vertices $\{v_1,v_2,v_3\}$ with weight $w(v_1)=\alpha (G^*-N[u'])-\alpha (G^*-N[\{u,u'\}])$, $w(v_2)=\alpha (G^*-N[u])-\alpha (G^*-N[\{u,u'\}])$ and $w(v_3)=\alpha (G^*)-\alpha (G^*-N[u])$, and add five new edges $uv_1$, $v_1v_2$, $v_2u'$, $uv_3$ and $u'v_3$. It holds that

$$ \alpha (G)=\alpha (G')+\alpha (G^*-N[\{u,u'\}]). $$

Reduction Rule 12

(R12). For a vertex-cut $\{u,u'\}$ of size two with a connected component $G^*$ in $G-\{u,u'\}$ such that $2\delta _3+\delta _2\le \sum _{v\in G^*}\delta _{d_G(v)}\le 10$, we construct the graph $G'$ in Lemma 4, replace G with $G'$, and add $\alpha (G^*-N[\{u,u'\}])$ to $M_c$.

3.4 Analyzing Reduction Rules

It is easy to see that each application of our reduction rules can be executed in polynomial time. We also show that

Lemma 5

The measure p will not increase after applying any reduction rule.

Definition 1

An instance is reduced, if no reduction rule can be applied.

Lemma 6

(*) In a reduced instance, any two degree-2 vertices in different chains have at most one common chain-neighbor of degree at least 3, and each cycle contains at least three vertices of degree $\ge 3$.

Lemma 7

(*) For a triangle C in a reduced instance, each vertex in C is a vertex of degree $\ge 3$ and it has a chain-neighbor of degree at least 3 not in C.

4 Branching Rules

4.1 Two Branching Rules

We have two branching rules. The first branching rule is to branch on a vertex v by considering two cases: (i) there is a maximum weighted independent set in G which does not contain v; (ii) every maximum weighted independent set in G contains v. For the former case, we simply delete v from the graph. For the latter case, by Lemma 2 we know that we can include the set $S_v$ confining v in the independent set. So we delete $N[S_v]$ from the graph.

Branching Rule 1

(Branching on a vertex). Branch on a vertex v to generate two sub instances by either deleting v from the graph or deleting $N[S_v]$ from the graph and adding $w(S_v)$ to $M_c$.

Since each independent set contains at most two vertices in each 4-cycle, we have the second rule.

Branching Rule 2

(Branching on a 4-cycle). Branch on a 4-cycle $v_1v_2v_3v_4$ to generate two sub instances by deleting either $\{v_1,v_3\}$ or $\{v_2,v_4\}$ from G.

4.2 The Analysis and Some Properties

The hardest part is to analyze how much we can decrease the measure in each sub-branch of a branching operation. Usually, we need to deeply analyze the local graph structure and use case-analysis. Here we try to summarize some common properties. The following notations will be frequently used in the whole paper.

Let S be a vertex subset in a reduced graph G. We use $G_{-S}$ to denote the graph after deleting S from G and iteratively applying R1 to R4 until none of them can be applied. We use $R_S$ to denote the set of deleted vertices during applying R1 to R4 on $G-S$. Then $G_{-S}=G-(S\cup R_S)$. We also use $e_S$ to denote the number of edges between $S\cup R_S$ and $V\setminus (S\cup R_S)$ in G. We have the following lemmas for some bounds on $p(G)-p(G_{-S})$. Note that $G_{-S}$ may not be a reduced graph because of reduction rules from R5 to R12 and we may further apply reduction rules to further decrease the measure p.

Lemma 8

(*) It holds that

$$\begin{aligned} p(G) - p(G_{-S})\ge \sum _{u\in S\cup R_S}\delta _{d_G(u)}+e_S \delta _3^{<-1>}. \end{aligned}$$

(3)

In some cases, we can not use the bound in (3) directly, since we may not know the vertex set $R_S$. So we also consider some special cases and relaxed bounds.

Lemma 9

(*) Let $S=\{v\}$ be a set of a vertex of degree $\ge 3$. We have that

$$p(G)-p(G_{-S})\ge \delta _{d(v)}+\sum _{u\in N(v)}\delta _{d(u)}^{<-1>}+q_2\delta _{3}^{<-1>},$$

where $q_2$ is the number of degree-2 vertices in N(v).

Lemma 10

(*) If $S\cup R_S$ contains N[v] for some vertex v of degree $\ge 3$, then we have that

$$p(G)-p(G_{-S})\ge \sum _{u\in N[v]}\delta _{d(u)}+q_2\delta _{3}^{<-1>},$$

where $q_2$ is the number of degree-2 vertices in N(v).

Recall that we use $\mathcal {C}(G')$ to denote the set of connected components of the graph $G'$. We can easily observe the following lemma, which will be used to prove several bounds on $p(G) - p(G_{-S})$.

Lemma 11

Let S be a vertex subset. Let $S'$ be a subset of $S\cup R_S$ and $R'=S\cup R_S\setminus S'$. The number of edges between $S\cup R_S$ and $V\setminus (S\cup R_S)$ is $e_S$, and the number of edges between $S'$ and $V\setminus S'$ is k. For any component $H\in \mathcal {C}(G[R'])$, the number of edges between $S'$ and H is $l_H$ and the number of edges between H and $N(S\cup R_S)$ is $r_H$. We have that

$$k-e_S=\sum _{H\in \mathcal {C}(G[R'])}(l_H-r_H).$$

Furthermore, for any component $H\in \mathcal {C}(G[R'])$ containing only degree-2 vertices, it holds that $l_H-r_H=0$ or 2.

Lemma 12

(*) For any subset $S'\subseteq S\cup R_S$ with k edges between $S'$ and $V\setminus S'$, it holds that

Lemma 13

(*) Assume that a reduced graph G has a maximum degree 3 and has no 3 or 4-cycles. For any subset $S'\subseteq S\cup R_S$ with k edges between $S'$ and $V\setminus S'$, if the diameter of the induced graph $G[S']$ is 2, then it holds that either $p(G) - p(G_{-S})> 10$ or

Lemma 14

(*) Assume that a reduced graph G has a maximum degree 3, and each cycle C in it contains at least five vertices, where at least four vertices are degree-3 vertices. For any subset $S'\subseteq S\cup R_S$ with k edges between $S'$ and $V\setminus S'$, if each path P in the induced graph $G[S']$ contains either at most three vertices or at most two degree-3 vertices, then it holds either $p(G) - p(G_{-S})> 10$ or

5 The Algorithm

Now we describe the main steps of the algorithm. When the algorithm executes one step, we assume that all previous steps can not be applied.

Step 1

(Applying Reductions). If the instance is not reduced, iteratively apply reduction rules in order, i.e., when one reduction rule is applied, no reduction rule with a smaller index can be applied on the graph.

Step 2

(Solving Small Components). If there is a connected component $G^*$ of G such that $p(G^*)\le 10$, solve the component $G^*$ directly and return $\alpha (G-G^*)+\alpha (G^*)$.

Step 3

(Branching on Vertices of Degree $\ge 5$). If there is a vertex v with degree $d(v)\ge 5$, then branch on v with Branching Rule 1 by either excluding v from the independent set or including $S_v$ in the independent set.

Lemma 15

(*) Step 3 followed by applications of reduction rules creates a branching vector covered by [5.368, 7.248].

Step 4

(Branching on 4-Cycles with Chords). If there is a 4-cycle $C=v_1v_2v_3v_4$ with a chord $v_1v_3\in E$, then branch on the 4-cycle with Branching Rule 2 by excluding either $\{v_1,v_3\}$ or $\{v_2,v_4\}$ from the independent set.

Lemma 16

(*) Step 4 followed by applications of reduction rules creates a branching vector covered by one of $[3\delta _4+\delta _3^{<-1>}, 4\delta _4+ 2\delta _3^{<-1>}]=[5.496,7.744]~~\text{ and }$ $[4\delta _4, 2 \delta _4+2 \delta _3+2 \delta _2]=[6.496,6].$

Step 5

(Branching on Degree-4 Vertices). If there is a degree-4 vertex v, then branch on it with Branching Rule 1 by either excluding v from the independent set or including $S_v$ in the independent set.

Lemma 17

(*) Step 5 followed by applications of reduction rules creates a branching vector covered by one of [5.624, 5.624], [5.248, 6], [4.872, 6.624], [4.496, 7.248], and [4.12, 7.872].

Step 6

(Branching on Other 4-Cycles). If there is a 4-cycle $C=v_1v_2v_3v_4$, then branch on the 4-cycle with Branching Rule 2 by excluding either $\{v_1,v_3\}$ or $\{v_2,v_4\}$ from the independent set.

Lemma 18

(*) Step 6 followed by applications of reduction rules creates a branching vector covered by $[6\delta _3-2\delta _2, 6\delta _3-2\delta _2]=[5.248,5.248].$

Step 7

(Branching on Triangles). If there is a triangle $C=v_1v_2v_3$, where we assume without loss of generality that $w(v_1)\ge \max \{w(v_2), w(v_3)\}$ and $v_1$ is chain-adjacent to a degree-3 vertex $u\ne v_2, v_3$, then branch on u with Branching Rule 1.

Lemma 19

(*) Step 7 followed by applications of reduction rules creates a branching vector covered by one of $[6\delta _3 -3\delta _2, 7\delta _3+\delta _2]=[4.872,7.376]$ and $[6\delta _3 -2\delta _2, 5\delta _3+2\delta _2]=[5.248,5.752].$

Step 8

(Branching on Cycles Containing Three Degree-3 Vertices). If there is a cycle C containing exactly three degree-3 vertices $\{v_1,v_2,v_3\}$, where we assume without loss of generality that $v_1$ is chain-adjacent to a degree-3 vertex $u\ne v_2,v_3$, then branch on u with Branching Rule 1.

Lemma 20

(*) Step 8 followed by applications of reduction rules can create a branching vector covered by one of $[6\delta _3-4\delta _2,8\delta _3-2\delta _2]=[4.496,7.248],$ $[6\delta _3-3\delta _2,6\delta _3-\delta _2]=[4.872,5.624]$, and $[6\delta _3-2\delta _2,6\delta _3-2\delta _2]=[5.248,5.248].$

Step 9

(Branching on Degree-3 Vertices with Two Degree-2 Neighbors). If there is degree-3 vertex u having two degree-2 neighbors and one degree-3 neighbor v, then branch on v with Branching Rule 1.

Lemma 21

(*) Step 9 followed by applications of reduction rules creates a branching vector covered by one of $[4\delta _3-\delta _2, 8\delta _3-\delta _2]=[3.624,7.624]$, $[4\delta _3, 8\delta _3-4\delta _2]=[4,6.496]$, and $[4\delta _3+\delta _2, 6\delta _3]=[4.376,6]$.

Step 10

(Branching on Degree-3 Vertices of a Mixed Case). If a degree-3 vertex u without degree-3 neighbors is chain-adjacent to a degree-3 vertex v with exactly two degree-3 neighbors, then branch on v with Branching Rule 1.

Lemma 22

(*) Step 10 followed by applications of reduction rules creates a branching vector covered by $[4\delta _3, 8\delta _3-2\delta _2]=[4,7.248].$

Step 11

(Branching on Degree-3 Vertices With At Least Two Degree-3 Neighbors). If there is a connected component H containing a degree-3 vertex with at least two degree-3 neighbors, we let u be the vertex of the maximum weight in H and let v be a degree-3 neighbor of u, and branch on v with Branching Rule 1.

Lemma 23

(*) Step 11 followed by applications of reduction rules creates a branching vector covered by one of $[4\delta _3-\delta _2, 8\delta _3-\delta _2]=[3.624,7.624]$, and $[4\delta _3, 8\delta _3-4\delta _2]=[4,6.496].$

Step 12

(Branching on Other Degree-3 Vertices). Pick up an arbitrary degree-3 vertex v and branch on it with Branching Rule 1.

Lemma 24

(*) Step 12 followed by applications of reduction rules creates a branching vector covered by $[4\delta _3+6\delta _2,4\delta _3+6\delta _2]=[6.256,6.256].$

It is easy to see that above steps cover all the cases. Among all the branching vectors, the bottleneck ones are $[4\delta _3,8\delta _3-4\delta _2]=[4,6.496]$ in Lemma 21, $[4\delta _3+\delta _2,6\delta _3]=[4.376,6]$ in Lemma 21, and $[4\delta _3, 8\delta _3-4\delta _2]=[4,6.496]$ in Lemma 23. All of them have a branching factor of 1.14427. So we get that

Theorem 1

Maximum Weighted Independent Set can be solved in $O^*(1.1443^p)$ time and polynomial space.

By Lemma 1 and Theorem 1, we get that

Corollary 1

Maximum Weighted Independent Set in graphs with average degree x can be solved in $O^*(1.1443^{(0.624x-0.872)n})$ time and polynomial space.

Let $x=3$ in Lemma 1, we get that $p\le n$ and the following result.

Theorem 2

Maximum Weighted Independent Set in graphs with the average degree at most 3 can be solved in $O^*(1.1443^n)$ time and polynomial space.