# A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem

Authors: Peng Du; Yuan Zhang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Maximum weight independent set (MWIS) is a combinatorial optimization problem that naturally arises in many applications especially wireless networking. This paper studies distributed approximation algorithms for finding MWIS in a general graph. In the proposed algorithm, each node keeps exchanging messages with neighbors in which each message contains partial solutions of the MWIS optimization program. A parameterH is introduced to achieve different tradeoff between approximation accuracy and space complexity. Theoretical analysis shows that the proposed algorithm is guaranteed to converge to an approximate solution after finite iterations; specifically, the proposed algorithm is guaranteed to converge to the optimal solution with H
=
+
∞. Simulation results confirm the effectiveness of the proposed distributed algorithm in terms of weight sum, message size, and convergence performance.


---

## Body

## 1. Introduction

Consider a graphG
=
(
V
,
E
) with a set V of nodes and a set E of edges. For each node i
∈
V, there is a positive weight w
i. A subset of V can be represented by binary variable x
i, 1
≤
i
≤
|
V
|, where x
i is 1 if i is in the subset and 0 otherwise. A subset is called an independent set if no two nodes in the subset are connected by an edge. We are interested in finding the maximum weight independent set (MWIS) [1], which can be expressed as an integer program:(1)
m
a
x
∑
i
w
i
x
i
s
.
t
.
x
k
+
x
i
≤
1
,
k
,
i
∈
E
x
i
∈
0,1
,
i
∈
V
.The MWIS problem has been extensively studied in the literature. For example, it is known to be solvable in polynomial time for many cases including perfect graphs [2], interval graphs [2], disk graphs [3], claw-free graphs [4], fork-free graphs [5], trees [6], sparse random graphs [7, 8], circle graphs [9], and growth-bounded graphs [10]. Moreover, there has been extensive work on approximating the MWIS [11], and specialized algorithms have been developed for exactly computing the MWIS [12–15].Further, the MWIS problem naturally arises in many applications, especially wireless networking, which require distributed solutions. For example [16–18], in scenarios involving resource scheduling in wireless networks that lack a centralized infrastructure and where nodes can only communicate with local neighbors, the MWIS problem needs to be solved in a distributed manner. Fundamentally, any two wireless nodes that transmit at the same resource will interfere with each other if they are located close-by. The scheduling problem is to decide which nodes should transmit at the given resource so that there is no interference and nodes with long queue length are given priority. If each node is given a weight equal to the queue length, it is optimal to schedule the set of nodes with the highest total weight. If a conflict graph is made, with an edge between each pair of interfering nodes, the scheduling problem is exactly the MWIS problem for the conflict graph. The lack of an infrastructure and the local nature of communication require a distributed algorithm for solving the MWIS problem.There are three types of distributed algorithms for MWIS problem: greedy algorithms, carrier sense random multiple access (CSMA) algorithms, and message-passing algorithms.For greedy algorithms, several simple distributed algorithms for MWIS have been proposed in the literature [19–22]. These algorithms are based on the greedy principle and require only knowledge of the local topology at each node. However, due to the inherent difficulty of the MWIS problem, greedy algorithms are not guaranteed to obtain the optimal solution for general graph.For random multiple access algorithms, several CSMA-based algorithms have been proposed [23–26]. These algorithms are distributed, are of low complexity, and are easy to implement. They use a random access scheme according to which a link seizes the channel with a probability that increases exponentially with a certain link-dependent weight. As explained in [27], these schemes perform sampling over independent sets of the graph and converge to the optimal MWIS in graphs with large weights. However, according to [28], message-passing algorithms can achieve significantly smaller aggregate long-run average queue length than CSMA algorithms.Several message-passing algorithms for producing a feasible solution to the MWIS were proposed in [28–34]. For example, in [30], Sanghavi et al. show that a simple modification of max product becomes gradient descent on the dual of the linear programming associated with the MWIS problem and converges to the dual optimum. They also develop a message-passing algorithm that recovers the primal MWIS solution from the output of the descent algorithm and show that the MWIS estimate obtained using these two algorithms in conjunction is correct when the graph is bipartite and the MWIS is unique. In [31], it has been shown that polynomial time methods exist for perfect graphs which include bipartite graphs and many others. Further, in [29], message-passing methods were developed for perfect graphs. Additionally, it is worth mentioning that message-passing methods have also been successfully applied to solve the maximum weight matching (MWM) problem [35–38].This paper studies this problem and proposes a new distributed algorithm for the general graph. The proposed algorithm runs iteratively in which each node receives messages from its neighbors, updates the message of its own, and then broadcasts the message to the neighbors. During the message update procedure, each node shall first combine all received messages into a single one and then delete some elements from the message to control the size of the message. Theoretical analysis and computer simulation show that the proposed algorithm will converge after finite iterations and can achieve tradeoff between approximation accuracy and space complexity.The rest of the paper is outlined as follows. In Section2, some useful notations are introduced. In Section 3, a new distributed algorithm for MWIS is proposed. In Section 4, the theoretical analysis of the proposed distributed algorithm including convergence and optimality is presented. Section 5 reports simulation results of the proposed algorithm and its comparison to the existing distributed MWIS algorithms. Finally, concluding remarks are given in Section 6.


## 2. Notation

This section introduces some notations which will be used throughout this paper. The symbols used in this paper are summarized in the List of Symbols.


### 2.1. Partial Solution

LetX
=
{
x
n
,
1
≤
n
≤
V
} denote the full variable set of the MWIS problem. Assuming Y is a subset of X, a partial solution of the MWIS problem is expressed as(2)
p
=
x
k
=
v
k
,
x
k
∈
Y
,where v
k is 0 or 1. We call Y the partial variable set of the MWIS problem. The objective associated with p is expressed as(3)
V
p
=
∑
x
k
∈
Y
w
k
·
v
k
.Further, given a partial variable set Y, the partial solution set can be expressed as(4)
Ω
=
p
j
,
1
≤
j
≤
Ω
,where(5)
p
j
=
x
k
=
v
j
,
k
,
x
k
∈
Y
.To help understand this, we use the graph shown in Figure1 as an example. For this graph, there are four nodes and the weights are w
1
=
3, w
2
=
4, w
3
=
5, and w
4
=
5. The full variable set X
=
{
x
1
,
x
2
,
x
3
,
x
4
}. Assuming the partial variable set Y
=
{
x
1
,
x
2
}
⊆
X, then p
=
{
x
1
=
1
,
x
2
=
0
} is a partial solution of the MWIS problem. The objective associated with this partial solution is V
p
=
w
1
·
x
1
+
w
2
·
x
2
=
3.Figure 1
An example of the graph.


### 2.2. Combination

For any two partial solutionsp
1
=
{
x
k
=
v
k
,
x
k
∈
Y
1
} and p
2
=
{
x
l
=
u
l
,
x
l
∈
Y
2
}, if there exists a common variable x
i
∈
Y
1
∩
Y
2 so that v
i
≠
u
i, then we say these two partial solutions are contradictory; otherwise, if there does not exist such common variable, we say these two partial solutions are compatible. For more than two partial solutions, if there exist two partial solutions which are contradictory, we say these partial solutions are contradictory; otherwise, we say these partial solutions are compatible.Then, for a number of partial solutionsp
j, 1
≤
j
≤
J, the combination operation over them is defined as follows:(6)
⨂
1
≤
j
≤
J
⁡
p
j
≜
∅
,
they  are  contradictory
⋃
1
≤
j
≤
J
p
j
,
they  are  compatible
.Finally, for a number of partial solution sets Ω
i
=
{
p
i
,
j
,
1
≤
j
≤
Ω
i
}, 1
≤
i
≤
I, the combination operation over them is defined as(7)
⨂
1
≤
i
≤
I
⁡
Ω
i
≜
⨂
1
≤
i
≤
I
⁡
p
i
,
j
,
p
i
,
j
∈
Ω
i
.We continue to use the graph shown in Figure1 as the example. For convenience, let p
1
=
{
x
1
=
0
,
x
2
=
0
}, p
2
=
{
x
1
=
1
,
x
2
=
0
}, p
3
=
{
x
1
=
0
,
x
4
=
0
}, and p
4
=
{
x
1
=
1
,
x
4
=
0
}. Firstly, for p
2 and p
3, since x
1 has different values in p
2 and p
3 (i.e., x
1
=
1 in p
2 and x
1
=
0 in p
3), we say p
2 and p
3 are contradictory and we have p
2
⊗
p
3
=
∅. Secondly, for p
2 and p
4, since there is no common variable which has different values in p
2 and p
4, we say p
2 and p
4 are compatible and we have p
2
⊗
p
4
=
{
x
1
=
1
,
x
2
=
0
,
x
4
=
0
}. Thirdly, assuming Ω
1
=
{
p
1
,
p
2
} and Ω
2
=
{
p
3
,
p
4
}, it can be verified that Ω
1
⊗
Ω
2
=
{
{
x
1
=
0
,
x
2
=
0
,
x
4
=
0
}
,
{
x
1
=
1
,
x
2
=
0
,
x
4
=
0
}
}.


### 2.3. Truncation

For a partial solution setΩ
=
{
p
j
,
1
≤
j
≤
Ω
}, sort the elements in Ω by the values of the objective so that V
p
1
≥
V
p
2
≥
⋯
≥
V
p
Ω. Define the truncation operation over Ω as(8)
T
r
u
n
c
Ω
,
H
≜
p
j
,
1
≤
j
≤
min
⁡
Ω
,
H
,where H is a parameter.We continue to use the graph shown in Figure1 as the example. Assume Ω
=
{
p
1
,
p
2
,
p
3
}, where p
1
=
{
x
1
=
0
,
x
2
=
1
}, p
2
=
{
x
1
=
1
,
x
2
=
0
}, and p
3
=
{
x
1
=
0
,
x
2
=
0
}. It can be verified that V
p
1
=
4, V
p
2
=
3, and V
p
3
=
0. Therefore, we have V
p
1
≥
V
p
2
≥
V
p
3. If we set H
=
2, then we have T
r
u
n
c
(
Ω
,
H
)
=
{
p
1
,
p
2
}. That is, p
3 is deleted from Ω.


### 2.4. Feasible Partial Solution

AssumingY is a subset of X, define the associated constraint set as(9)
T
Y
=
x
i
+
x
k
≤
1
,
x
i
∈
Y
,
k
∈
N
i
,which contains all constraints involving variables in Y. Then, define the associated feasible partial solution set(10)
F
Y
,
T
Y
=
v
1
:
v
1
≻
T
Y
,where v
1
=
(
v
k
:
x
k
∈
Y
) and v
1
≻
T
(
Y
) represents the notion that v
1 satisfies the constraints in T
(
Y
). We have the following two lemmas.Lemma 1.
For two subsetsY
1 and Y
2, one has(11)
F
Y
1
,
T
Y
1
⊗
F
Y
2
,
T
Y
2
=
F
Y
1
∪
Y
2
,
T
Y
1
∪
Y
2
.Proof.
See AppendixA.Lemma 2.
ForK subsets Y
i, 1
≤
i
≤
K, one has(12)
⨂
1
≤
i
≤
K
⁡
F
Y
i
,
T
Y
i
=
F
⋃
1
≤
i
≤
K
Y
i
,
T
⋃
1
≤
i
≤
K
Y
i
.Proof.
See AppendixB.We continue to use the graph shown in Figure1 as the example. For two subsets Y
1
=
{
x
1
} and Y
2
=
{
x
4
}, we have T
(
Y
1
)
=
{
x
1
+
x
2
≤
1
,
x
1
+
x
4
≤
1
} and T
(
Y
2
)
=
{
x
1
+
x
4
≤
1
,
x
3
+
x
4
≤
1
}. On the one hand, there are five elements in F
(
Y
1
,
T
(
Y
1
)
), (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
0,1
,
1
), and (
1,0
,
0
), and five elements in F
(
Y
2
,
T
(
Y
2
)
), (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
1,0
,
0
), and (
1,1
,
0
). It can be verified that F
(
Y
1
,
T
(
Y
1
)
)
⊗
F
(
Y
2
,
T
(
Y
2
)
) contains eight elements: (
0,0
,
0,0
), (
0,0
,
1,0
), (
0,0
,
0,1
), (
0,1
,
0,0
), (
0,1
,
1,0
), (
0,1
,
0,1
), (
1,0
,
0,0
), and (
1,0
,
1,0
). On the other hand, we have Y
1
∪
Y
2
=
{
x
1
,
x
4
} and T
(
Y
1
∪
Y
2
)
=
{
x
1
+
x
2
≤
1
,
x
1
+
x
4
≤
1
,
x
3
+
x
4
≤
1
}. It can be verified that F
(
Y
1
∪
Y
2
,
T
(
Y
1
∪
Y
2
)
) also contains the same eight elements. Therefore, Lemma 1 is correct for this example.


## 2.1. Partial Solution

LetX
=
{
x
n
,
1
≤
n
≤
V
} denote the full variable set of the MWIS problem. Assuming Y is a subset of X, a partial solution of the MWIS problem is expressed as(2)
p
=
x
k
=
v
k
,
x
k
∈
Y
,where v
k is 0 or 1. We call Y the partial variable set of the MWIS problem. The objective associated with p is expressed as(3)
V
p
=
∑
x
k
∈
Y
w
k
·
v
k
.Further, given a partial variable set Y, the partial solution set can be expressed as(4)
Ω
=
p
j
,
1
≤
j
≤
Ω
,where(5)
p
j
=
x
k
=
v
j
,
k
,
x
k
∈
Y
.To help understand this, we use the graph shown in Figure1 as an example. For this graph, there are four nodes and the weights are w
1
=
3, w
2
=
4, w
3
=
5, and w
4
=
5. The full variable set X
=
{
x
1
,
x
2
,
x
3
,
x
4
}. Assuming the partial variable set Y
=
{
x
1
,
x
2
}
⊆
X, then p
=
{
x
1
=
1
,
x
2
=
0
} is a partial solution of the MWIS problem. The objective associated with this partial solution is V
p
=
w
1
·
x
1
+
w
2
·
x
2
=
3.Figure 1
An example of the graph.


## 2.2. Combination

For any two partial solutionsp
1
=
{
x
k
=
v
k
,
x
k
∈
Y
1
} and p
2
=
{
x
l
=
u
l
,
x
l
∈
Y
2
}, if there exists a common variable x
i
∈
Y
1
∩
Y
2 so that v
i
≠
u
i, then we say these two partial solutions are contradictory; otherwise, if there does not exist such common variable, we say these two partial solutions are compatible. For more than two partial solutions, if there exist two partial solutions which are contradictory, we say these partial solutions are contradictory; otherwise, we say these partial solutions are compatible.Then, for a number of partial solutionsp
j, 1
≤
j
≤
J, the combination operation over them is defined as follows:(6)
⨂
1
≤
j
≤
J
⁡
p
j
≜
∅
,
they  are  contradictory
⋃
1
≤
j
≤
J
p
j
,
they  are  compatible
.Finally, for a number of partial solution sets Ω
i
=
{
p
i
,
j
,
1
≤
j
≤
Ω
i
}, 1
≤
i
≤
I, the combination operation over them is defined as(7)
⨂
1
≤
i
≤
I
⁡
Ω
i
≜
⨂
1
≤
i
≤
I
⁡
p
i
,
j
,
p
i
,
j
∈
Ω
i
.We continue to use the graph shown in Figure1 as the example. For convenience, let p
1
=
{
x
1
=
0
,
x
2
=
0
}, p
2
=
{
x
1
=
1
,
x
2
=
0
}, p
3
=
{
x
1
=
0
,
x
4
=
0
}, and p
4
=
{
x
1
=
1
,
x
4
=
0
}. Firstly, for p
2 and p
3, since x
1 has different values in p
2 and p
3 (i.e., x
1
=
1 in p
2 and x
1
=
0 in p
3), we say p
2 and p
3 are contradictory and we have p
2
⊗
p
3
=
∅. Secondly, for p
2 and p
4, since there is no common variable which has different values in p
2 and p
4, we say p
2 and p
4 are compatible and we have p
2
⊗
p
4
=
{
x
1
=
1
,
x
2
=
0
,
x
4
=
0
}. Thirdly, assuming Ω
1
=
{
p
1
,
p
2
} and Ω
2
=
{
p
3
,
p
4
}, it can be verified that Ω
1
⊗
Ω
2
=
{
{
x
1
=
0
,
x
2
=
0
,
x
4
=
0
}
,
{
x
1
=
1
,
x
2
=
0
,
x
4
=
0
}
}.


## 2.3. Truncation

For a partial solution setΩ
=
{
p
j
,
1
≤
j
≤
Ω
}, sort the elements in Ω by the values of the objective so that V
p
1
≥
V
p
2
≥
⋯
≥
V
p
Ω. Define the truncation operation over Ω as(8)
T
r
u
n
c
Ω
,
H
≜
p
j
,
1
≤
j
≤
min
⁡
Ω
,
H
,where H is a parameter.We continue to use the graph shown in Figure1 as the example. Assume Ω
=
{
p
1
,
p
2
,
p
3
}, where p
1
=
{
x
1
=
0
,
x
2
=
1
}, p
2
=
{
x
1
=
1
,
x
2
=
0
}, and p
3
=
{
x
1
=
0
,
x
2
=
0
}. It can be verified that V
p
1
=
4, V
p
2
=
3, and V
p
3
=
0. Therefore, we have V
p
1
≥
V
p
2
≥
V
p
3. If we set H
=
2, then we have T
r
u
n
c
(
Ω
,
H
)
=
{
p
1
,
p
2
}. That is, p
3 is deleted from Ω.


## 2.4. Feasible Partial Solution

AssumingY is a subset of X, define the associated constraint set as(9)
T
Y
=
x
i
+
x
k
≤
1
,
x
i
∈
Y
,
k
∈
N
i
,which contains all constraints involving variables in Y. Then, define the associated feasible partial solution set(10)
F
Y
,
T
Y
=
v
1
:
v
1
≻
T
Y
,where v
1
=
(
v
k
:
x
k
∈
Y
) and v
1
≻
T
(
Y
) represents the notion that v
1 satisfies the constraints in T
(
Y
). We have the following two lemmas.Lemma 1.
For two subsetsY
1 and Y
2, one has(11)
F
Y
1
,
T
Y
1
⊗
F
Y
2
,
T
Y
2
=
F
Y
1
∪
Y
2
,
T
Y
1
∪
Y
2
.Proof.
See AppendixA.Lemma 2.
ForK subsets Y
i, 1
≤
i
≤
K, one has(12)
⨂
1
≤
i
≤
K
⁡
F
Y
i
,
T
Y
i
=
F
⋃
1
≤
i
≤
K
Y
i
,
T
⋃
1
≤
i
≤
K
Y
i
.Proof.
See AppendixB.We continue to use the graph shown in Figure1 as the example. For two subsets Y
1
=
{
x
1
} and Y
2
=
{
x
4
}, we have T
(
Y
1
)
=
{
x
1
+
x
2
≤
1
,
x
1
+
x
4
≤
1
} and T
(
Y
2
)
=
{
x
1
+
x
4
≤
1
,
x
3
+
x
4
≤
1
}. On the one hand, there are five elements in F
(
Y
1
,
T
(
Y
1
)
), (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
0,1
,
1
), and (
1,0
,
0
), and five elements in F
(
Y
2
,
T
(
Y
2
)
), (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
1,0
,
0
), and (
1,1
,
0
). It can be verified that F
(
Y
1
,
T
(
Y
1
)
)
⊗
F
(
Y
2
,
T
(
Y
2
)
) contains eight elements: (
0,0
,
0,0
), (
0,0
,
1,0
), (
0,0
,
0,1
), (
0,1
,
0,0
), (
0,1
,
1,0
), (
0,1
,
0,1
), (
1,0
,
0,0
), and (
1,0
,
1,0
). On the other hand, we have Y
1
∪
Y
2
=
{
x
1
,
x
4
} and T
(
Y
1
∪
Y
2
)
=
{
x
1
+
x
2
≤
1
,
x
1
+
x
4
≤
1
,
x
3
+
x
4
≤
1
}. It can be verified that F
(
Y
1
∪
Y
2
,
T
(
Y
1
∪
Y
2
)
) also contains the same eight elements. Therefore, Lemma 1 is correct for this example.


## 3. The Proposed Algorithm

The proposed algorithm is performed in an iterative manner. LetN
i denote the set of neighbors of node i. At each iteration t, node i sends a message M
i
t to each neighbor in N
i, where message M
i
t is actually a partial solution set. The details of the proposed distributed algorithm are presented as follows.


### 3.1. Algorithm

The operation of nodei consists of two steps, which are presented in sequence as follows.Step 1 (the combination operation).
Nodei receives the message M
j
t
-
1 from each neighbor j
∈
N
i and then generates a partial solution set as(13)
Q
i
t
=
⨂
j
∈
N
i
∪
i
⁡
M
j
t
-
1
.Specifically, for t
=
1, we set(14)
Q
i
1
=
F
X
i
1
,
T
X
i
1
,where(15)
X
i
1
=
x
i
∪
x
k
,
k
∈
N
i
.For convenience, we express Q
i
t as(16)
Q
i
t
=
p
j
,
1
≤
j
≤
Q
i
t
,where X
i
t is the partial variable set associated with node i in the tth iteration.Step 2 (the truncation operation).
The number of elements ofQ
i
t can be very large. A parameter H is introduced to control the space complexity. Node i only keeps H out of the total Q
i
t elements and generates the message(17)
M
i
t
=
T
r
u
n
c
Q
i
t
,
H
,where H is a parameter known by each node. Node i broadcasts the message M
i
t to its neighbors.Each node shall repeat the above steps until convergence. As proved in Section4 (Theorem 5), this process will converge after finite iterations. Upon convergence, assume the message node i sending to each neighbor is M
i. Let X
i denote the partial variable set associated with M
i. We can write M
i
=
{
p
j
,
1
≤
j
≤
M
i
} and p
j
=
{
x
k
=
v
j
,
k
,
x
k
∈
X
i
}. Node i shall determine(18)
j
∗
=
a
r
g
max
j
⁡
V
p
jand estimate(19)
x
i
∗
=
v
j
∗
,
i
.If we setH
=
+
∞, node i will not delete any partial solution in the truncation operation, and the algorithm will converge to the optimal solution as proved in Section 4 (Theorem 6). However, the message size will increase exponentially with the node number V as shown in Section 5 (Figure 2). On the other hand, for general H, node i will delete a part of the partial solutions in the truncation operation to keep the message size small, and the algorithm will converge to an approximate solution with acceptable loss of optimality as shown in Section 5 (Figures 3 and 4). Therefore, the proposed algorithm can achieve different tradeoff between optimality and complexity.Figure 2
The average message size performance.Figure 3
The average weight sum performance.Figure 4
The average weight sum performance.


### 3.2. Example 1: The Synchronous Case

To illustrate the above procedure, we use the graph shown in Figure1 as an example. It can be verified that the maximum weight independent set is {
n
o
d
e
2
,
n
o
d
e
4
} (i.e., x
1
=
0, x
2
=
1, x
3
=
0, and x
4
=
1) and the associated objective is 9. For this example, we assume all nodes operate synchronously.For each nodei, it will send message M
i
t to its neighbors at the tth iteration. We will assume H
=
+
∞ and H
=
3, respectively.Case 1 (H
=
+
∞).
We take node 1 as the example. Initially,t
=
1, message Q
1
1 contains five elements: (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
0,1
,
1
), and (
1,0
,
0
). Then, node 1 performs the truncation operation to generate M
1
1. Since H
=
+
∞, we have M
1
1
=
Q
1
1, as shown in Table 1(a). For t
=
2, since H
=
+
∞, node 1 has M
1
2
=
Q
1
2
=
M
1
1
⊗
M
2
1
⊗
M
4
1 in which there are seven elements, (
0,0
,
0,0
), (
0,0
,
0,1
), (
0,0
,
1,0
), (
0,1
,
0,0
), (
0,1
,
0,1
), (
1,0
,
0,0
), and (
1,0
,
1,0
), as shown in Table 1(b). For t
≥
3, the set M
1
t does not change any more. We pick the solution with the highest objective, that is, the solution x
1
=
0, x
2
=
1, x
3
=
0, and x
4
=
1, which is exactly the optimal solution.Table 1
An example withH
=
+
∞.
(a)
x
1
x
2
x
3
x
4
t
=
1
M
1
t
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
M
2
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
3
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
4
t
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
(b)
x
1
x
2
x
3
x
4
t
=
2
M
1
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
2
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
3
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
4
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0Case 2 (H
=
3).
We still take node 1 as the example. Initially,t
=
1, message Q
1
1 contains five elements: (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
0,1
,
1
), and (
1,0
,
0
). Then, node 1 performs the truncation operation to generate M
1
1. Since H
=
3, there are three elements in M
1
1, (
0,0
,
1
), (
0,1
,
0
), and (
0,1
,
1
), as shown in Table 2(a). For t
=
2, after similar operations, there is only one element in M
1
2, (
0,1
,
0,1
), as shown in Table 2(b). For t
≥
3, the set M
1
t does not change any more. We pick the solution with the highest objective, that is, the solution x
1
=
0, x
2
=
1, x
3
=
0, and x
4
=
1, which is exactly the optimal solution.Table 2
An example withH
=
3.
(a)
x
1
x
2
x
3
x
4
t
=
1
M
1
t
0
0
1
0
1
0
0
1
1
M
2
t
0
0
1
0
1
0
1
0
1
M
3
t
0
0
1
0
1
0
1
0
1
M
4
t
0
0
1
0
1
0
1
1
0
(b)
x
1
x
2
x
3
x
4
t
=
2
M
1
t
0
1
0
1
M
2
t
0
1
0
1
M
3
t
1
0
1
0
0
0
1
0
0
1
0
1
M
4
t
0
0
0
1
0
1
0
1Comparing these two cases, we can observe that, forH
=
3, the node will delete some partial solutions in the truncation operation to keep the message size small.


### 3.3. Example 2: The Asynchronous Case

The proposed algorithm can be run fully asynchronously. This is due to the fact that the combination operation, which is the core of the algorithm, does not require all nodes to act synchronously. We use the graph shown in Figure1 again as the example. For this example, we assume node 1 is the one which is not synchronized with other nodes. Specifically, we assume that node 1 will not generate messages until t
=
2. We use the proposed algorithm to solve this problem. To focus on the problem raised in this comment, we assume H
=
+
∞ so that the proposed algorithm can be expressed as the following iterative equation:(20)
M
i
t
=
⨂
j
∈
N
i
∪
i
⁡
M
j
t
-
1
,where M
i
t is the message broadcasted by node i in the tth iteration. The running process of the algorithm is described as follows.Initially, fort
=
1, according to (14) and (15), the message generated by each node can be expressed as M
1
1
=
∅, M
2
1
=
F
(
X
2
1
,
T
(
X
2
1
)
), M
3
1
=
F
(
X
3
1
,
T
(
X
3
1
)
), and M
4
1
=
F
(
X
4
1
,
T
(
X
4
1
)
). Therefore, node 1 generates message M
1
1 which contains no elements, node 2 generates message M
2
1 which contains five elements, (
x
1
,
x
2
,
x
3
)
=
(
0,0
,
0
), (
x
1
,
x
2
,
x
3
)
=
(
0,0
,
1
), (
x
1
,
x
2
,
x
3
)
=
(
0,1
,
0
), (
x
1
,
x
2
,
x
3
)
=
(
1,0
,
0
), and (
x
1
,
x
2
,
x
3
)
=
(
1,0
,
1
), and so on, as shown in Table 3(a).Table 3
An asynchronous example.
(a)
x
1
x
2
x
3
x
4
t
=
1
M
1
t
M
2
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
3
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
4
t
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
(b)
x
1
x
2
x
3
x
4
t
=
2
M
1
t
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
M
2
t
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
M
3
t
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
M
4
t
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
(c)
x
1
x
2
x
3
x
4
t
=
3
M
1
t
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
2
t
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
3
t
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
M
4
t
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0Then, fort
=
2, according to (20), the message generated by each node can be expressed as M
1
2
=
F
(
X
1
1
,
T
(
X
1
1
)
), M
2
2
=
M
2
1
⊗
M
3
1, M
3
2
=
M
3
1
⊗
M
2
1
⊗
M
4
1, and M
4
2
=
M
4
1
⊗
M
3
1. It can be verified that M
1
1 contains five elements: (
x
1
,
x
2
,
x
4
)
=
(
0,0
,
0
), (
x
1
,
x
2
,
x
4
)
=
(
0,0
,
1
), (
x
1
,
x
2
,
x
4
)
=
(
0,1
,
0
), (
x
1
,
x
2
,
x
4
)
=
(
0,1
,
1
), and (
x
1
,
x
2
,
x
4
)
=
(
1,0
,
0
); M
2
2 contains eight elements; M
3
2 contains seven elements; and M
4
2 contains eight elements, as shown in Table 3(b).Fort
≥
3, according to (20), the message generated by each node can be expressed as M
1
t
=
M
1
t
-
1
⊗
M
2
t
-
1
⊗
M
4
t
-
1, M
2
t
=
M
2
t
-
1
⊗
M
3
t
-
1
⊗
M
1
t
-
1, M
3
t
=
M
3
t
-
1
⊗
M
2
t
-
1
⊗
M
4
t
-
1, and M
4
t
=
M
4
t
-
1
⊗
M
3
t
-
1
⊗
M
1
t
-
1. It can be verified that the message M
1
t contains seven elements, and so on, as shown in Table 3(c). We pick the solution with the highest objective, that is, the solution (
x
1
,
x
2
,
x
3
,
x
4
)
=
(
0,1
,
0,1
), which is exactly the optimal solution.


## 3.1. Algorithm

The operation of nodei consists of two steps, which are presented in sequence as follows.Step 1 (the combination operation).
Nodei receives the message M
j
t
-
1 from each neighbor j
∈
N
i and then generates a partial solution set as(13)
Q
i
t
=
⨂
j
∈
N
i
∪
i
⁡
M
j
t
-
1
.Specifically, for t
=
1, we set(14)
Q
i
1
=
F
X
i
1
,
T
X
i
1
,where(15)
X
i
1
=
x
i
∪
x
k
,
k
∈
N
i
.For convenience, we express Q
i
t as(16)
Q
i
t
=
p
j
,
1
≤
j
≤
Q
i
t
,where X
i
t is the partial variable set associated with node i in the tth iteration.Step 2 (the truncation operation).
The number of elements ofQ
i
t can be very large. A parameter H is introduced to control the space complexity. Node i only keeps H out of the total Q
i
t elements and generates the message(17)
M
i
t
=
T
r
u
n
c
Q
i
t
,
H
,where H is a parameter known by each node. Node i broadcasts the message M
i
t to its neighbors.Each node shall repeat the above steps until convergence. As proved in Section4 (Theorem 5), this process will converge after finite iterations. Upon convergence, assume the message node i sending to each neighbor is M
i. Let X
i denote the partial variable set associated with M
i. We can write M
i
=
{
p
j
,
1
≤
j
≤
M
i
} and p
j
=
{
x
k
=
v
j
,
k
,
x
k
∈
X
i
}. Node i shall determine(18)
j
∗
=
a
r
g
max
j
⁡
V
p
jand estimate(19)
x
i
∗
=
v
j
∗
,
i
.If we setH
=
+
∞, node i will not delete any partial solution in the truncation operation, and the algorithm will converge to the optimal solution as proved in Section 4 (Theorem 6). However, the message size will increase exponentially with the node number V as shown in Section 5 (Figure 2). On the other hand, for general H, node i will delete a part of the partial solutions in the truncation operation to keep the message size small, and the algorithm will converge to an approximate solution with acceptable loss of optimality as shown in Section 5 (Figures 3 and 4). Therefore, the proposed algorithm can achieve different tradeoff between optimality and complexity.Figure 2
The average message size performance.Figure 3
The average weight sum performance.Figure 4
The average weight sum performance.


## 3.2. Example 1: The Synchronous Case

To illustrate the above procedure, we use the graph shown in Figure1 as an example. It can be verified that the maximum weight independent set is {
n
o
d
e
2
,
n
o
d
e
4
} (i.e., x
1
=
0, x
2
=
1, x
3
=
0, and x
4
=
1) and the associated objective is 9. For this example, we assume all nodes operate synchronously.For each nodei, it will send message M
i
t to its neighbors at the tth iteration. We will assume H
=
+
∞ and H
=
3, respectively.Case 1 (H
=
+
∞).
We take node 1 as the example. Initially,t
=
1, message Q
1
1 contains five elements: (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
0,1
,
1
), and (
1,0
,
0
). Then, node 1 performs the truncation operation to generate M
1
1. Since H
=
+
∞, we have M
1
1
=
Q
1
1, as shown in Table 1(a). For t
=
2, since H
=
+
∞, node 1 has M
1
2
=
Q
1
2
=
M
1
1
⊗
M
2
1
⊗
M
4
1 in which there are seven elements, (
0,0
,
0,0
), (
0,0
,
0,1
), (
0,0
,
1,0
), (
0,1
,
0,0
), (
0,1
,
0,1
), (
1,0
,
0,0
), and (
1,0
,
1,0
), as shown in Table 1(b). For t
≥
3, the set M
1
t does not change any more. We pick the solution with the highest objective, that is, the solution x
1
=
0, x
2
=
1, x
3
=
0, and x
4
=
1, which is exactly the optimal solution.Table 1
An example withH
=
+
∞.
(a)
x
1
x
2
x
3
x
4
t
=
1
M
1
t
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
M
2
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
3
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
4
t
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
(b)
x
1
x
2
x
3
x
4
t
=
2
M
1
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
2
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
3
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
4
t
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0Case 2 (H
=
3).
We still take node 1 as the example. Initially,t
=
1, message Q
1
1 contains five elements: (
0,0
,
0
), (
0,0
,
1
), (
0,1
,
0
), (
0,1
,
1
), and (
1,0
,
0
). Then, node 1 performs the truncation operation to generate M
1
1. Since H
=
3, there are three elements in M
1
1, (
0,0
,
1
), (
0,1
,
0
), and (
0,1
,
1
), as shown in Table 2(a). For t
=
2, after similar operations, there is only one element in M
1
2, (
0,1
,
0,1
), as shown in Table 2(b). For t
≥
3, the set M
1
t does not change any more. We pick the solution with the highest objective, that is, the solution x
1
=
0, x
2
=
1, x
3
=
0, and x
4
=
1, which is exactly the optimal solution.Table 2
An example withH
=
3.
(a)
x
1
x
2
x
3
x
4
t
=
1
M
1
t
0
0
1
0
1
0
0
1
1
M
2
t
0
0
1
0
1
0
1
0
1
M
3
t
0
0
1
0
1
0
1
0
1
M
4
t
0
0
1
0
1
0
1
1
0
(b)
x
1
x
2
x
3
x
4
t
=
2
M
1
t
0
1
0
1
M
2
t
0
1
0
1
M
3
t
1
0
1
0
0
0
1
0
0
1
0
1
M
4
t
0
0
0
1
0
1
0
1Comparing these two cases, we can observe that, forH
=
3, the node will delete some partial solutions in the truncation operation to keep the message size small.


## 3.3. Example 2: The Asynchronous Case

The proposed algorithm can be run fully asynchronously. This is due to the fact that the combination operation, which is the core of the algorithm, does not require all nodes to act synchronously. We use the graph shown in Figure1 again as the example. For this example, we assume node 1 is the one which is not synchronized with other nodes. Specifically, we assume that node 1 will not generate messages until t
=
2. We use the proposed algorithm to solve this problem. To focus on the problem raised in this comment, we assume H
=
+
∞ so that the proposed algorithm can be expressed as the following iterative equation:(20)
M
i
t
=
⨂
j
∈
N
i
∪
i
⁡
M
j
t
-
1
,where M
i
t is the message broadcasted by node i in the tth iteration. The running process of the algorithm is described as follows.Initially, fort
=
1, according to (14) and (15), the message generated by each node can be expressed as M
1
1
=
∅, M
2
1
=
F
(
X
2
1
,
T
(
X
2
1
)
), M
3
1
=
F
(
X
3
1
,
T
(
X
3
1
)
), and M
4
1
=
F
(
X
4
1
,
T
(
X
4
1
)
). Therefore, node 1 generates message M
1
1 which contains no elements, node 2 generates message M
2
1 which contains five elements, (
x
1
,
x
2
,
x
3
)
=
(
0,0
,
0
), (
x
1
,
x
2
,
x
3
)
=
(
0,0
,
1
), (
x
1
,
x
2
,
x
3
)
=
(
0,1
,
0
), (
x
1
,
x
2
,
x
3
)
=
(
1,0
,
0
), and (
x
1
,
x
2
,
x
3
)
=
(
1,0
,
1
), and so on, as shown in Table 3(a).Table 3
An asynchronous example.
(a)
x
1
x
2
x
3
x
4
t
=
1
M
1
t
M
2
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
3
t
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
M
4
t
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
(b)
x
1
x
2
x
3
x
4
t
=
2
M
1
t
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
M
2
t
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
M
3
t
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
M
4
t
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
(c)
x
1
x
2
x
3
x
4
t
=
3
M
1
t
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
2
t
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
M
3
t
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
M
4
t
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0Then, fort
=
2, according to (20), the message generated by each node can be expressed as M
1
2
=
F
(
X
1
1
,
T
(
X
1
1
)
), M
2
2
=
M
2
1
⊗
M
3
1, M
3
2
=
M
3
1
⊗
M
2
1
⊗
M
4
1, and M
4
2
=
M
4
1
⊗
M
3
1. It can be verified that M
1
1 contains five elements: (
x
1
,
x
2
,
x
4
)
=
(
0,0
,
0
), (
x
1
,
x
2
,
x
4
)
=
(
0,0
,
1
), (
x
1
,
x
2
,
x
4
)
=
(
0,1
,
0
), (
x
1
,
x
2
,
x
4
)
=
(
0,1
,
1
), and (
x
1
,
x
2
,
x
4
)
=
(
1,0
,
0
); M
2
2 contains eight elements; M
3
2 contains seven elements; and M
4
2 contains eight elements, as shown in Table 3(b).Fort
≥
3, according to (20), the message generated by each node can be expressed as M
1
t
=
M
1
t
-
1
⊗
M
2
t
-
1
⊗
M
4
t
-
1, M
2
t
=
M
2
t
-
1
⊗
M
3
t
-
1
⊗
M
1
t
-
1, M
3
t
=
M
3
t
-
1
⊗
M
2
t
-
1
⊗
M
4
t
-
1, and M
4
t
=
M
4
t
-
1
⊗
M
3
t
-
1
⊗
M
1
t
-
1. It can be verified that the message M
1
t contains seven elements, and so on, as shown in Table 3(c). We pick the solution with the highest objective, that is, the solution (
x
1
,
x
2
,
x
3
,
x
4
)
=
(
0,1
,
0,1
), which is exactly the optimal solution.


## 4. Theoretical Analysis

This section presents the theoretical analysis results of the proposed distributed algorithm.Recall thatX
i
t is the partial variable set associated with node i in the tth iteration. Firstly, we have the following two lemmas.Lemma 3.
For generalH, one has(21)
X
i
t
=
⋃
k
∈
N
i
∪
i
X
k
t
-
1
,
(22)
M
i
t
⊆
F
X
i
t
,
T
X
i
t
.Proof.
We prove these two equations by induction ont. Initially, t
=
1, according to the algorithm, we have M
i
1
=
T
r
u
n
c
(
Q
i
1
,
H
)
⊆
Q
i
1
=
F
(
X
i
1
,
T
(
X
i
1
)
), where X
i
1
=
{
x
i
}
∪
{
x
k
,
k
∈
N
i
}. Therefore, this lemma holds for t
=
1. Suppose this lemma is correct for t
≥
2. For t
+
1, we have M
i
t
+
1
⊆
Q
i
t
+
1
=
⊗
k
∈
N
i
∪
{
i
}
M
k
t. Assuming this lemma is correct for t
≥
2, we have Q
i
t
+
1
⊆
⊗
k
∈
N
i
∪
{
i
}
F
(
X
k
t
,
T
(
X
k
t
)
). Applying Lemma 2, we then have Q
i
t
+
1
⊆
F
(
∪
k
∈
N
i
∪
{
i
}
X
k
t
,
T
(
∪
k
∈
N
i
∪
{
i
}
X
k
t
)
). Since X
i
t
+
1 is the partial variable set associated with node i in the (
t
+
1
)th iteration, we know that X
i
t
+
1
=
∪
k
∈
N
i
∪
{
i
}
X
k
t, which means that (21) is correct for t
+
1. Further, we have M
i
t
+
1
⊆
Q
i
t
+
1
⊆
F
(
X
i
t
+
1
,
T
(
X
i
t
+
1
)
), which means that (22) is correct for t
+
1. This completes the proof of this lemma.Lemma 4.
ForH
=
+
∞, one has(23)
M
i
t
=
F
X
i
t
,
T
X
i
t
.Proof.
We prove this equation by induction ont. Initially, t
=
1, according to the algorithm, since H
=
+
∞, we have M
i
1
=
Q
i
1
=
F
(
X
i
1
,
T
(
X
i
1
)
), where X
i
1
=
{
x
i
}
∪
{
x
k
,
k
∈
N
i
}. Therefore, this lemma holds for t
=
1. Suppose this lemma is correct for t
≥
2. For t
+
1, we firstly have Q
i
t
+
1
=
⊗
k
∈
N
i
∪
{
i
}
M
k
t. Assuming this lemma is correct for t
≥
2, we have Q
i
t
+
1
=
⊗
k
∈
N
i
∪
{
i
}
F
(
X
k
t
,
T
(
X
k
t
)
). Applying Lemma 2, we then have Q
i
t
+
1
=
F
(
∪
k
∈
N
i
∪
{
i
}
X
k
t
,
T
(
∪
k
∈
N
i
∪
{
i
}
X
k
t
)
). Since X
i
t
+
1 is the partial variable set associated with node i in the (
t
+
1
)th iteration, we have X
i
t
+
1
=
∪
k
∈
N
i
∪
{
i
}
X
k
t. Since H
=
+
∞, we finally have M
i
t
+
1
=
Q
i
t
+
1
=
F
(
X
i
t
+
1
,
T
(
X
i
t
+
1
)
), which means that (23) is correct for t
+
1. This completes the proof of this lemma.Based on these two lemmas, we have the following two theorems. Letd
i
a
m
(
G
) denote the diameter of the graph G.Theorem 5.
For generalH, the proposed algorithm will converge to a feasible solution after 2
×
d
i
a
m
(
G
)
+
1 iterations.Proof.
According to (21), X
i
t contains nodes to which the shortest distance from i is t. Since d
i
a
m
(
G
) is the longest distance between any two nodes, we have X
i
t
=
X for t
≥
d
i
a
m
(
G
)
+
1. Therefore, since t
=
d
i
a
m
(
G
)
+
2, we have M
i
t
=
⊗
k
∈
N
i
∪
{
i
}
M
k
t
-
1. For convenience, define M
~
i
≜
M
i
d
i
a
m
(
G
)
+
1. Therefore, since t
=
2
×
d
i
a
m
(
G
)
+
1, we have M
i
t
=
⊗
k
∈
V
M
~
k which will not change any more. Therefore, the proposed algorithm will converge after 2
×
d
i
a
m
(
G
)
+
1 iterations.
According to (22), due to X
i
t
=
X for t
≥
d
i
a
m
(
G
)
+
1, we have M
i
d
i
a
m
(
G
)
+
1
⊆
F
(
X
,
T
(
X
)
) for t
≥
d
i
a
m
(
G
)
+
1. That is, each element in M
~
i is a feasible full solution. Therefore, for t
≥
2
×
d
i
a
m
(
G
)
+
1, each element in M
i
t
=
⊗
k
∈
V
M
~
k is a feasible full solution. According to the algorithm, node i will estimate x
∗
=
a
r
g
m
a
x
x
∈
M
i
t
w
H
x, where x
=
(
x
1
,
…
,
x
N
) and w
=
(
w
1
,
…
,
w
N
). Since each element contained in M
i
t is a feasible full solution of the MWIS problem, x
∗ must be feasible. Therefore, the proposed algorithm will converge to a feasible full solution after 2
×
d
i
a
m
(
G
)
+
1 iterations.Theorem 6.
ForH
=
+
∞, the proposed algorithm will converge to the optimal solution after d
i
a
m
(
G
)
+
1 iterations.Proof.
Fort
≥
d
i
a
m
(
G
)
+
1, since d
i
a
m
(
G
) is the longest distance between any two nodes, we have X
i
t
=
X. Thus, according to (23), for t
≥
d
i
a
m
(
G
)
+
1, we have M
i
t
=
F
(
X
,
T
(
X
)
). Therefore, the algorithm is converged after d
i
a
m
(
G
)
+
1 iterations. Since node i will estimate x
∗
=
a
r
g
m
a
x
x
∈
F
(
X
,
T
(
X
)
)
w
H
x, where F
(
X
,
T
(
X
)
) covers all feasible solutions of the MWIS problem, x
∗ must be the optimal one. Therefore, the proposed algorithm will converge to the optimal solution after d
i
a
m
(
G
)
+
1 iterations.Theoretical analysis results show that the proposed algorithm is guaranteed to converge to an independent set and the tradeoff between approximation accuracy and algorithm complexity is controlled by parameterH, which are confirmed by the simulation results reported in Section 5.


## 5. Performance Evaluation

In this section, we evaluate the proposed algorithm via computer simulations. We first describe the simulation methodology and then present and analyze the simulation results.We develop a simulator based on MATLAB. In the simulator, a total ofV nodes are randomly distributed over a 10-meter × 10-meter flat field. For each node, the weight is a random number ranging from 0 to 1. For any two nodes, if the distance is less than 6 meters, there will be an edge connecting them. Thus, we have generated a general graph. For this graph, we use five methods to find its MWIS. The first is to use the full version of the proposed algorithm, the second is to use the general version of the proposed algorithm with parameter H ranging from 5 to 30, the third is to use the greedy algorithm proposed in [19], the fourth is to use the message-passing algorithm proposed in [30], and the fifth is to use MATLAB function bintprog to solve the integer program in (1). For the first two methods, we collect four metrics that characterize the performance of the proposed algorithm: (1) the weight sum of the output set, (2) the iteration number needed to converge, (3) the diameter of the graph, and (4) the message size, that is, the number of ME contained in each message, upon convergence. For the other two methods, we only collect the weight sum of the output set. The procedure is repeated 1000 times for each value of V, each time with a new generated graph and weights, and results are averaged out.We first report that the proposed algorithm is convergent for all simulation runs, and the output set is always independent. Then, we present the simulation results obtained from computer experiments, which are organized in four figures. Figure2 shows the average message size upon convergence as the node number |
V
| varied. Specifically, it is worth mentioning that since the message-passing algorithm does not always converge and the output set is not always independent, we only collect the results when the message-passing algorithm converges and the output set is independent. In this figure, for H
=
+
∞, the message size grows exponentially with node number, while for general H the message size is well controlled. Figures 3 and 4 show the average weight sum performance as the node number |
V
| and parameter H varied. In these two figures, the proposed algorithm with general H will converge to an approximate solution with acceptable loss of optimality as parameter H is appropriately selected. Additionally, in Figure 3, the curve corresponding to H
=
+
∞ coincides with the curve of the optimal solution. Thus, the optimality part of Theorem 6 is verified. Finally, Figure 5 shows the average iteration number needed to converge as the node number |
V
| varied. In this figure, the curve corresponding to H
=
+
∞ is always under the upper bound predicted by Theorem 6 (i.e., the diameter plus 1), while the curves corresponding to the general H are always under the upper bound predicted by Theorem 5 (i.e., two times the diameter plus 1). Thus, Theorem 5 and the convergence part of Theorem 6 are verified. Simulation results show that the proposed algorithm with H
=
+
∞ is a distributed optimal algorithm, while the proposed algorithm with general H is a distributed approximate algorithm which by changing parameter H can achieve different tradeoff between approximation accuracy and space complexity.Figure 5
The average iteration number performance.Finally, we empirically study how to set value for the parameterH. Actually, we need a way to estimate a good H for a given weighted graph. We propose to set H as the integer times of the number of nodes. The simulation results are summarized in Table 4. According to the simulation results, we suggest to set H as 2–4 times the number of nodes.Table 4
Simulation results with differentH.
V
H
The final solution
The optimal solution
V
=
15
H
=
1
⋅
V
1.79
2.21
H
=
2
⋅
V
2.21
H
=
4
⋅
V
2.21
V
=
25
H
=
1
⋅
V
1.62
2.61
H
=
2
⋅
V
2.55
H
=
4
⋅
V
2.60
V
=
35
H
=
1
⋅
V
1.87
3.02
H
=
2
⋅
V
2.56
H
=
4
⋅
V
2.99


## 6. Conclusions

A new distributed algorithm for finding the maximum weight independent set in a general graph is presented. The proposed algorithm runs iteratively in which each node receives a message form each neighbor, updates the message of its own, and sends it to each neighbor. It is shown that the proposed algorithm will converge to an independent set after finite iterations and can achieve different tradeoff between approximation accuracy and space complexity. Specifically, the proposed algorithm withH
=
+
∞ is guaranteed to converge to the optimal solution.



---

*Source: 9790629-2016-09-06.xml*