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.