For a graph where each node is assigned a weight, 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. 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.