数理解析研究所講究録1093 巻 1999 年 45-50

45

On greedy algorithms for
maximum weighted independent set problem
Shuichi Sakai, Mitsunori Togasaki, Koichi Yamazaki*

Department of Computer Science Gunma University
1-5-1 Tenjin-cho, Kiryu zip:376-8515, Gunma, Japanshuichi,togasaki,koichi@comp.cs.gunma-u.ac.jp

Introduction

1

The optimization problem Maximum (Weighted) Independent Set
is one of most important problems in computer science $[16, 14]$ . It is well known that the decision problem for MIS is-complete. In the eighties, many natural graph classes for which MIS allows to have a polynomial
time algorithm were found, and many other natural classes for which MIS remains-complete werealso found [7]. In the nineties, approximateness have received much attention. With the advance ofstudy of relationship between nonapproximation and interactive proofs, the results on hardness of MIS
to approximate have been improved. It is known that for MIS there is a polynominal time approximation algorithm with a ratio of(which is of the form $n^{1-o(1)}$ ) $[4]$ . Recently
have
shown that MIS is hard to approximate within
for any. For graphs with degree boundedby , MIS is known to be MAX SNP-complete [15] and can be approximable withinfor every$\epsilon>0[2]$ . For bounded degree weighted graphs, a polynominal time approximation
algorithm with aratio ofis known. [11].
Greedy strategy is one of the most common heuristic method for optimization problems. For MIS,
two simple greedy algorithms were investigated. One is c\‘alled $MIN$, which selects a vertex of minimum
degree, removes it and its neighbors from the graph, and iterates this process on the remaining graphuntil no vertex rernains. The other is called $MAX$, which deletes a vertex of maximum degree until noedge remains. Halld\’orsson and Radhakrishnan showed that $MIN$ achieves approximation ratio
and this bound is tight [12]. Griggs [10] and Chv\’atal and C.
proved independently that
$MAX$ outputs an independent set of size at least
for any graph . This implies that theapproximation ratio is at most $\Delta+1$ . Halld\’orsson and Radhakrishnan showed that the ratio is at.
least
In this paper, we consider three simple greedy algorithms and two parallel algorithms for MWIS.
In section 2, we review terminology and concepts used throughout the paper. In section 3, first we give
two simple algorithms WMIN and GWMAX which are generalization of $MIN$ and $MAX$ respectively.
Then we show that both greedy algorithms output an independent set of weight.
This can be considered as a natural extension of Tura’n’s theorem. We also give another simple greedy
algorithm, which outputs an independent set of weight. This can be also$(\mathrm{M}\mathrm{I}\mathrm{S}(\mathrm{M}\mathrm{W}\mathrm{I}\mathrm{S}))$$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$$o( \frac{n}{(\log n)^{2}})$$\mathrm{H}^{\mathrm{o}}\mathrm{a}\mathrm{S}\mathrm{t}\mathrm{a}\mathrm{d}$$n^{1-\epsilon}$$\epsilon[13]$$\Delta$$\frac{\Delta+3}{5+\epsilon}$$\frac{\Delta+2}{3}$$\frac{\Delta+2}{3}$$\mathrm{M}\mathrm{c}\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{d}[5]$$\sum_{v\in V}\frac{1}{d(v)+1}$$G$$\frac{\Delta+1}{2}[12]$$G$$\geq\sum_{v\in V(G})^{\frac{W(v)}{d(v)+1}}$$\geq\sum_{v\in V(}G)^{\frac{W(v)^{2}}{\mathrm{L}_{u\in(}^{\urcorner}N_{G}^{+}v\rangle W(u)}}$thought as an extension of Tur\’an’s theorem. In section 4, we present two parallel algorithms PWMIN
and PWMAX, which are parallelization of $MIN$ and $MAX$ respectively.
The last author was supported by the Scientific Grant-in-Aid for Encouragement of Young Scientistsof Education, Science, Sports and Culture of Japan.
*$\mathrm{h}\mathrm{o}\mathrm{m}$Ministry

46

2Definitions

Let $G=(V, E, W)$ be a weighted undirected graph without loops and multiple edges, where is the$2^{V}arrow N^{+}$
set of vertices, is the set of edges, and $W$ is the vertex weighting function such that $W$ :(i.e. each vertex has a positive integral weight), $W(u)\geq 0$ for all $u\in V$ and $W(S)= \sum_{u\in S}W(u)$ for. We also use the notation $V(G)$ and $E(G)$ to denote the set of vertices and edges in . For a$W(S)$ andare referred as the weight and size of respectively. is unweighted if
subset$u\inV$
is an independent set of if for any two vertices $v\in I$ ,. A subset$W(u)=1$ for all$\{u, v\}\not\in E$ . An independent setof is maximum if there is no independent set $I’$ of such that(i.e. $W(I)=\alpha(G)$$W(I)<W(I’)$ . We denote the weight of maximum independent set of by
by $V’,$ $d_{G}(u)$$G[V’]$
ofinducedsubgraphthedenotefor a maximum independent set of ). Let$G,$ $N_{G}(v)$ theof
degreeaveragetheinvertexthe maximum degree ofthe degree of vertex. If is understood, then we often omit the inscriptionneighborhoods of , and$N_{G}(v)$. For an independent set algorithm $A,$ $A(G)$ is the weight of the, andin $d_{G}(u),$.
of is defined bysolution obtained by on graph . The performance ratio
$V$

$E$

$G$

$S\subseteq V$

$G$

$S$

$|S|$

$S\subseteq V,$$G$$I\subseteq V$

$I$

$G$

$I$

$G$

$u,$

$G$

$G$

$u,$

$G,\overline{d}_{G}$$\Delta_{G}$

$G$

$G$

$N_{G}^{+}(v)\{v\}\mathrm{U}N_{G}(v)$$v$$\alpha(G)$$G$$N_{G}^{+}(v)$$\Delta_{G},\overline{d}_{G},$

$A$

$G$

$A$

$\rho_{A}$$\rho_{A}=\mathrm{m}\mathrm{a}\mathrm{x}c\frac{\alpha(G)}{A(G)}$3

Greedy algorithms and extension of Tur\’an’s theorem

3.1

Known results

The following theorem is known as Tur\’an’s theorem [3].

Theorem 3.1 For any unweighted graph$G$,$\alpha(G)\geq\frac{n}{\overline{d}_{G}+1}$.

Erd\"os showed that for unweighted graphs $MIN$ attains the above bound [6]. The following extensionof Theorem 3.1 was proved first by Wei and later by Alon and Spencer in a different way from Wei.
Theorem 3.2 For any unweighted graph$G$,$\alpha(G)\geq\sum_{v\epsilon V}\frac{1}{d(v)+1}$.

vertices [18]. Alon and
Wei demonstrated that $MIN$ outputs an independent set of at least
Spencer gave an elegant probabilistic proof of Theorem 3.2 [1], and Selkow improved the probabilistic
proof [17]. The probabilistic proof is nonconstructive, however. We can apply the probabilistic proof
to the case where graphs are weighted. Thus we have the next theorem.
$\sum_{v\in V^{\frac{1}{d(v)+1}}}$

Theorem 3.3 For any weighted graph$G$,$\alpha(G)\geq$$\sum$$\frac{W(v)}{d_{G}(v)+1}$.

$v\in V(G)$3.2

An extension of $MIN$

Let us consider the following framework of $MIN$ type algorithm.

47

Algorithm WMIN

:
:

INPUT
OUTPUTA weighted graph
A maximal independent set in
$G$

$G$

.

begin
$I:=\emptyset;i:=0;c_{i}:=G$ ;while
doChoose a vertex, say$I:=I\cup\{vi\}$ ;$V(G_{i})\neq\emptyset$$v_{i}$, in$G\dot{.}$$G_{i+1}:=G_{i}[V(Gi)-N_{G*}^{+}(v_{i})]$;;$i:=i+1$ ;odOutput ;end.
$I$

Theorem 3.4 In WMIN, if each $v_{i}(0\leq i\leq|I|)$ satisfies$\sum u\in N_{G}+.(v:)\frac{W(u)}{d_{G_{*}}.(u)+1}\leq W(v_{i})$such a node for any graph), then WMIN outputs an independent set of weight at least
We refer to a simple greedy algorithm (based on WMIN) in which a vertex
over all $u\in V(G_{i})$ is selected in each iteration as GWMIN.

Corollary 3.5 GWMIN outputs an independent set of weight at least$v$(there exists$\sum_{v\in V^{\frac{W(v)}{d_{G}(v)+1}}}$

maximizing$\sum_{v\in V^{\frac{W(v)}{d_{G}(v)+1}}}$.

$d_{G}.B_{u+}^{u}W\square 1$.

Theorem 3.6 $\Delta-1\leq p_{GWMIN}\leq\Delta+1$ .
$\square$

It seems to be worth noting that we cannot guarantee the performance if we pick up a vertex maximiz. The graph depicted in Fig.1 is a counterexample. In the graph,ing. If we$\frac{W(v)}{d_{G_{i}}(v)}$choose the vertex$\sum_{v\in V^{\frac{W(v)}{d(v)+1}}}=14$$v_{2}$(which maximizes$\frac{W(v)}{d(v)+1}$), we get the independent set

is 30. On the other hand, if we choose the vertex, and the total weight is 13.
set$v_{1}$(which maximizes$\{v_{1}, v_{3}, v_{4}\}$

Figure 1: A counterexample.

3.3

An extension of $MAX$

Let us consider the following framework of $MAX$ type algorithm.

$\{v_{2}\}$$\frac{W(v)}{d(v)}$, and the total weight), we get the independent

48

The next theorem is a generalization of the result of Griggs and Chv\’atal and C.
essence of the proof is the same as Griggs’s proof.
Theorem 3.7 In WMAX, if each $v_{i}(0\leq i\leq|V(G)-I|)$ satisfies
and $d_{G:}(v_{i})\neq 0$ there exists such a node for any graph such that$\mathrm{M}\mathrm{c}\mathrm{D}\mathrm{i}\mathrm{a}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{d}$. The$\sum_{u\in G}N(:v).\frac{W(u)}{d_{G}.(u)(d_{G}\dot{.}(u)+1)}\geq$

$G$

$($

$\dot{.}\frac{W(v)}{d_{G}(v)+1}$

outputs an independent set of weight at least$\sum_{v\in V^{\frac{W(v)}{d_{G}(v)+1}}}$$E(G)\neq\emptyset)_{j}$then WMAX.
$\square$

We refer to a simple greedy algorithm (based on WMAX) in which a vertex minimizing
for all $u\in V(G_{i})$ is selected in each iteration as GWMA X.

CoroUary 3.8 GWMAX outputs an independent set of weight at least
Corollary 3.9 A
weight at least$S\dot{i}mple$$\sum_{v\in V^{\frac{W(v)}{d_{G}(v)+1}}}$.

$\frac{W(u.)}{d_{G}.(u)(d_{G}(u)+1)}$

$v$

$.$

.

greedy algorithm (based on WMAX) in which outputs an independent set of$\sum_{v\in V^{\frac{W(v)}{d_{G}(v)+1}}}$,

Theorem 3.10 $\Delta\leq\rho GWMAX\leq\Delta+1$ .
$\square$

3.4

New greedy algorithm

Theorem 3.11 A simple greedy algorithm (based on WMIN) in which a vertex$v$maximizing$\mathrm{R}_{+}^{Wu}w\epsilon N_{G}.(\mathrm{u}))W(w$over all $u\in V(G_{i})$ , is selected in each iteration, outputs an independent set of weight at least$\sum_{v\in V()^{\frac{W(v)^{2}}{\sum_{u\in N_{G}^{+}()}vW(u)}}}c$.
$\square$If $W(v)=1$ for all $v\in V(G)$ (i.e. unweighted case), then$\sum_{v\in V(G})^{\frac{1}{d(v)+1}}$

4$\sum_{v\in V(G})^{\frac{W(v)^{2}}{\sum_{l\epsilon()}N_{G}^{+}vW(u)}}$is equal towhich is the bound of Tur\’an’s theorem.

Parallel algorithms

Goldberg and Spencer gave a parallel algorithm for MIS which finds an independent set of size at. In [12], Halld\’orsson and Radhakrishnan parallelized $MIN$. In this section, we show
least
that WMIN and WMAX can be parallelized using the same technique in [12]. Due to limitations of$\frac{n}{d_{G}+1}[9]$49space, we give only WMIN type parallel algorithm. It is easy to see that we can construct WMAX
type parallel algorithm in the same way. We assume the PRAM model.
Let $D_{G}(v)=W(v)- \sum_{u\in(v)^{\frac{W(u)}{d_{G}(u)+1}}}N^{+}G$ and. In orderto estimate roughly the number of vertices satisfying $D_{G}(v)\geq 0$ in Lemma 4.3 (in Lemma4.4), we need the following two propositions.
$\overline{D}c(v)=\sum_{u\in N_{G}(v)\ovalbox{\tt\small REJECT}\frac{W(v)}{d_{G}(v)+1}}d_{G}udW(u)Gu+1-$$\overline{D}_{G}(v)\geq 0$

Proposition 4.1 $\mathrm{E}[D_{G}(v)]=0$ .
ロ

The next proposition can be shown in the same way as proposition 4.1.

Proposition 4.2$\mathrm{E}[\overline{D}_{G}(v)]=0$.

Lemma 4.3 There are at leastvertices$\frac{|V(G)|}{1+(\Delta+1)!W_{\max}}$$\max dv\in V(G)G(v),$ $W_{\max}= \max_{v\in V(G})W(v)$$v$.

which satisfies $D_{G}(v)\geq 0$ , where $\Delta=$$\square$

Then the next lemma can be shown in the same way as lemma 4.3.
Lemma 4.4 There are at least$\max_{v\in V(c)^{d}}G(v),$$\frac{2|V(G)|}{2+\Delta(\Delta+1)!W_{\max}}$$W_{\max}= \max_{v\in V(}c)W(v)$vertices$v$

which $sati_{S}fieS\overline{D}G(v)\geq 0$ , where$\Delta=$.

If there are vertices and such that $D_{G}(v)\geq 0,$ $D_{G}(u)\geq 0$ , and the distance between and inis greater than three, then we can select and in parallel. Because the selection of does notaffect the selection of . This suggests the following natural WMIN type parallel algorithm, where
denote the graph obtained by taking the adjacency matrix of to the third power.
$u$

$v$

$G$

$u$

$u$

$v$

$v$

$u$

$G^{3}$$v$$G$

Algorithm PWMIN

INPUT

OUTPtjT::

A weighted graph $G$
A maximal independent set in $G$ .

begin;while $(V(G)\neq\emptyset)$ do$I$$:=.\emptyset$$SAT:=\{v\in V(G):D_{G}(v)\geq 0\}$ ;$H:=G^{3}[SAT]$ ;$NEW:=\mathrm{a}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{i}\mathrm{m}\mathrm{a}\mathrm{l}\backslash \mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{e}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{t}$set of $H$ ;$I:=I\cup NEW;$$G:=G[V(G)-\cup N_{G}+(v\epsilon NEWv)]$ ;od
Output ;end.
$I$From Lenma 4.3,
in each iteration. Since the maximum degree of $H$ is at
most, and $H$ is a maximal independent set, the size of NEW is atleast. Thus, the number of iterations is $O((1+(\Delta+1)!W_{\max})(\Delta^{3}+1)\log n)$ .
It is known that there is an algorithm which finds a maximal independent set of a graph in time$O((\log\Delta_{G})((\Delta_{G})2+\log^{*}n))$ using a linear number of processors [8]. As
and $W_{mav}$ do not dependon , we have the next theorem.
$|SAT| \geq\frac{|V(G)|}{1+(\Delta+1)!W_{\max}}$$\Delta+\Delta(\Delta-1)|V(G\mathrm{J}|+\Delta(\Delta-1)^{2}\leq\Delta^{3}$$\overline{(1+(\Delta+1)!W\max)(\Delta^{\mathrm{a}}+1)}$$G$$\Delta$$n$

Theorem 4.5 Let andbe fixed integers. For a graph for which the maximum degree is at mostand each vertex has a
integral weight bounded by, PWMIN outputs an independent
set of weight at leastin time $O((\Delta^{6}+1o\mathrm{g}^{*}n)(\log\Delta)(1+(\Delta+1)!W_{maoe})(\Delta^{3}+1)\log n)$using linear number of processors in the EREW model.
$\Delta$$W_{\max}$$\Delta$$p_{\mathit{0}Sitiv}e(v)$$\sum_{v\in V)}\overline{d_{G(v}+1}$$W_{\max}$50

References[1] N.Alon, J.H. Spencer, The probabilistic method, Wiley, New York, (1992).

[2] P. Berman and M. F\"urer, Approximating maximum independent set in bounded degree graphs,
it Proc. Fifth Ann. ACM-SIAM Symp. on Discrete Algorithms, (1994), pp.365-371.
[3] C. Berge, ”Graphes et Hypergraphes”, Dunod, Paris, (1970).
[4] R. Boppana and M. Halld\’orsson, Approximating maximum independent sets by excluding subgraphs, BIT, Vol. 32, (1992), pp.180-196.
[5] V. Chv\’atal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica, 12 (1),. pp.19..
26, (1992).
[6] P. Erd\"os, On the graph theorem of Tur\’an (in Hungarian), Mat. Lapok, 21, pp.249-251, (1970).

[7] Michael R. Garey, David S.Johnson, Computers and Intractability, A Guide to the Theory of. FREEMAN San Francisco”, (1979).
NP-Completeness,$‘ {}^{t}H$[8] A. V. Goldberg, S. A. Plotkin and G. E. Shannon, Parallel symmetry-breaking in sparse graphs,
it SIAM J. Disc. Math., Vol.1, (1988), pp.434-446.
[9] M. Goldberg and T. Spencer, An efficient parallel algorithm that finds independent sets of guaranteed size, SIAM J. Disc. Math., Vol. 6, (1993), pp.443-459.

[10] J. R. Griggs, Lower bounds on the independence number in terms of the degrees, J. Combin.
Theory Ser. B, 34, pp.22-39, (1983).

[11] Magn\’us M. Halld\’orsson, Approximation via partitioning, Technical Report IS-RR
School of Information Science, Japan Advanced Institute of Science and Technology,(1995).

$\mathit{9}\mathit{5}-\theta\theta \mathit{0}\mathit{3}F_{;}$$Hoku\gamma\cdot iku$,

[12] Magn\’us M. Halld\’orsson, Jaikumar Radhakrishnan, Greed is Good: Approximating Independent
Sets in Sparse and Bounded-degree Graphs, STOC, (1994), pp.439-448.
[13] Johan$\mathrm{H}^{\mathrm{o}}\mathrm{a}s\mathrm{t}\mathrm{a}\mathrm{d}$, Clique is hard to approximate within$n^{1-\epsilon}$, FOCS, (1996), pp.627-636.

[14] L. Lov\’asz, Stable set and polynomials, Discrete Mathematics, 124, (1994), pp.137-153.

[15] C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes,
J. Comput. System Sci. 43, (1991), pp.425-440.
[16] P. M. Pardalos and Jue Xue, The Maximum Clique Problem, Journal of Global Optimization 4,(1994), pp.301-328.

[17] S.M. Selkow, A probabilistic lower bound on the independence number of graphs, Discrete Mathematics, (1994), pp.363-365.
[18] V. K. Wei, A lower bound on the stability number of a simple graph, Technical Memorandum
No. 81-11217-9, Bell Laboratories, (1981).