In this section we introduce our solution for an important graph problemsMaximum Weighted Independent Setproblem, by using the techniques we have introduced in this chapter.
We assume each vertex in a graph is assigned with an int weight value. Given an undirected graphG= (V,E), an independent setSis a subset ofV that satisfies the condition: for any two virticesu,vinS, there is no such an edge(u,v)∈E.
The Maximum Weighted Independent Set problem is to find an independent set with the maximum total weight, which is defined as follows.
Definition 4.3 (Maximum Weighted Independent Set Problem). For an undirected graph G= (V,E), find an independent set S that the sum of weight of all vertices in S is maximum.
4.3.1 A Generate-Test Algorithm for Combinatorial Problems on Graphs
First, we express an algorithm for the MWIS problem in the form of the generate-test (a.k.a brute force) algorithm. We useg(vs,es) to represent an instance of graph with verticesvs and edgeses. We use functionw(v)denotes the weight ofv. Given a graphg(vs,es), we can generate all subsets ofvsand test whether a subset is a valid independent set, and then find the one with maximum sum of weight. We have defined the following functions to do so.
Functiongenerate::V →[V]lists all the possible selection sets and it is similar with function allSegmentsin Chapter 3.4.2.
Functiontest accepts two parameters: esof a graph g and one of its selection setxs, and
4.3 On Resolving Maximum Weighted Independent Set Problem 59 decides whetherxsis an independent set.
test::E→V →Bool
testes xs=not(any(λ x.memberx es) [ (u,v)|u←xs,v←xs])
Here, not::Bool→Bool and any::(a→Bool)→[a]→Bool are standard Haskell [16]
functions.
Functionweightcomputes the total weight of all the selected vertices in a selection set.
weight::V →Int
weightxs=reduce(+)◦(mapw)xs
Themwisgtfunction finds the one with the maximum weight of all the independent sets.
mwisgt::V →Int
mwisgtvs=maximum[weightxs|xs←generatevs,testes xs]
Here, functionmaximum::[a]→areturns the maximum element of a list, which is a stan-dard Haskell function.
In this example, if compute the MWIS problem on graphG= (V,E) naively as the above algorithm, it will take O(2|V|) time and actually not practical. An automatic optimization mechanism is developed by applying program transformation.
4.3.2 A Bottom-up Algorithm on Tree Decompositions
Using bottom-up dynamic programming algorithms on tree decompositions to solve MWIS has been discussed in [24, 62]. We first follow the idea and derive a bottom-up function mwison tree decomposition using the functions that we have defined in Section 4.3.1. We definegbt as the induced subgraph ofgon vertices inbt.
mwis::Tree→[(V,Int]
mwis(Leafbt) = [(xs,weightxs)|xs←generatebt,testesbt xs]
mwis(Nodebt children) = [(xs,weightxs+ (reduce(+)◦map(inheritxs) [t′|t′←children]))
|xs←generatebt,testesbt xs]
where
inheritxs t′=maximum[(value′−weight(intersectionxs xs′))
|(xs′,value′)←mwis(t′),consistent(xs,xs′)].
Functionmwisreturns a list of tuples of selection set xsand its corresponding weight sum.
Using graph in Figure 4.8 as the input, if we run functionmwison leafb0, it first generates all the possible selection sets of vertices in nodeb0, then tests if they are independent sets in the induced graphgb0. For example, on leafb0: mwis(Leaf b0) = [([],0),([1],1),([2],2)].
Similarly, on leafb1: mwis(Leaf b1) = [([],0),([4],4),([5],5)].
Functionconsistentchecks whether the same vertices appearing in two different nodes have the same selecting states. For each independent setxs, we choose theconsistentselection set which maximizes the contributed weight in each of its children.
consistent(xs,ys) = caseintersectxs ysof xs →True
ys →True _ →False
Carrying out functionmwison nodeb2, similar to the procedure on a leaf node, first gener-ates and tests all the possible independent sets in the induce graphgb2, then functioninherit is used to pass up the weight contributions of the vertices in its child nodes.
mwis(Nodeb2[b0,b1]) = [([ ],2+5),([2],2+5),([3],3+1+5),([4],1+4)].
Finally, we can compute the maximum sum by as follows:
valuemwis tree=maximum((map snd)(mwis tree)).
4.3 On Resolving Maximum Weighted Independent Set Problem 61 If the treewidth isw, there are at most 2(w+1) many generating marking ways on each node, and there areO(|V|)many nodes in a tree decomposition. The MWIS problem can be solved inO(|V| ·2(w+1))time using the bottom-up algorithm.
4.3.3 The Parallel Algorithm on Zippers
In the bottom-up algorithm, we need to remember the selecting statexsin the root of current subtree, which is used for the further computation of ancestors (testingconsistentcondition).
While on zippers, as shown in figure 4.9, we should remember the marking way of the leftmost and the rightmost subtree roots, for the leftward and rightward merging of partial results in the zipper.
We first duplicate the selecting state at the root of each subtree:
mwis′tree= [(xs,xs,value)|(xs,value)←mwis tree].
We modify the bottom-up functionmwison tree decompositionT to get a leftward sequen-tial functionmwisupont’s corresponding zipper.
mwisup = mwis′◦z2t
mwisup[(Node′bt children)] = mwis′(Nodebtchildren)
mwisup([a] ++ls) = [(xsa,xs′ls,valuea+valuels−weight(intersectxsaxs′ls)) | (xsa,xs′a,valuea)←mwisup a,
(xsls,xs′ls,valueb)←mwisup ls, consistentxs′axsls]
If the root of the rightmost subtree of zipper is considered as the root of its original tree decomposition, similar to mwisup, we can compute the Maximal-Weighted-Independent-Set in rightward manner (similarly to mwisup([a] ++ls), we can get mwisdown(ls++ [a]) from mwisdownlsand mwisdowna). When a function can be evaluated in both leftward and rightward manners, the third homomorphism theorem guarantees the existence of a parallel algorithm.
We, therefore, construct a parallel algorithm in the following way, with the definition of associative operator⊙and also themwisparfunction as follows.
mwispar = mwis′◦z2t
mwispar[(Node′btchildren)] = mwis′(Nodebt children) mwispar(a++b) = mwispara⊙mwisparb
= [(xsa,xs′b,valuea+valueb
−weight(intersectxs′axsb) | (xsa,xs′a,vlauea)←mwispara, (xsb,xs′b,valueb)←mwisparb, consistentxs′axsb]
Then maximum sum can be computed byvaluemwisdefined as follows:
valuemwistree=max((mapthd)(mwispar(walk tree))).
For each subtree, we can use functionmwis′to compute the partial results in parallel. Inde-pendent sets of two successive lists can be merged, if the selecting states of the rightmost root of the left list and the leftmost root of the right list areconsistent. Listing 4.2 shows a Java implementation of the MIWS-solving program.
If there are p processors, and the size of zipper is n, it takes O(|V| ·2(w+1)/p) time to compute the result of sub-list in parallel. A merging of two sub-list result takesO(22(w+1)) many computations. It takesO((n log n)/p·22(w+1)) in the merging procedure. From the practical view, the merging procedure is much faster, as the size of the pairs of selecting state can be largely reduced with theconsistent condition.
4.3.4 Evaluation
We implemented a shared memory version of MapReduce using Java multi-thread, to eval-uate our parallel algorithm for MWIS problem. Results are averaged over 5 tries.
Experiment Environment. All experiments are performed on a Linux (Ubuntu 12.04 64-bit) compute equipped with 8GB of RAM and two processors each with 4 cores (In-tel®Xeon®CPU E5620 @2.40GHz).
4.4 Related Work 63