January 23, 2014
We consider graphs with nodes representing decisions and edges representing conflicts among two decisions. Nodes are further assigned weights indicating the reward of the corresponding decision. In such a graph, the Maximum Weighted Independent Set (MWIS) problem is to select a set of nodes, no two of which are adjacent, with the largest possible total weight. This is equivalent to selecting a “conflict-free” set of decisions with maximal reward. MWIS is NP-hard.
I will present a new fully distributed algorithm consisting of two phases, each of which requires only local information and is based on message passing between nodes of the graph. The first phase solves a relaxation of MWIS, and the second phase constructs a feasible solution using a deterministic estimation algorithm. We show that our algorithm always outputs an optimal solution to MWIS for perfect graphs. I will illustrate the efficacy of the new algorithm in two very different applications domains: scheduling in wireless networks and protein docking.