Linear Programming for Maximum Independent Set Maximum independent set, or "maximum stable" set is one of classical NP-complete problems described in Richard Karp's 1972 paper "Reducibility Among Combinatorial Problems". Other NP-complete problems often have a simple reduction to it, for instance, p.3 of Tony Jebara's "MAP Estimation, Message Passing, and Perfect Graphs" shows how MAP inference in an arbitrary MRF reduces to Maximum Weight Independent Set. The problem asks to find the largest set of vertices in a graph, such that no two vertices are adjacent.
Read full article from Machine Learning, etc: Linear Programming for Maximum Independent Set
No comments:
Post a Comment