Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs.

We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph G = (V , E) , where each vertex v ∈ V has a weight w (v) and a cost c (v) , and a budget B. The goal is to find an independent set S ⊆ V in G such that ∑ v ∈ S c (v) ≤ B , which maximizes the total weight ∑ v ∈ S w (v). Since the problem on general graphs cannot be approximated within ratio | V | 1 − ɛ for any ɛ > 0 , BMWIS has attracted significant attention on graph families for which a maximum weight independent set can be computed in polynomial time. Two notable such graph families are bipartite and perfect graphs. BMWIS is known to be NP-hard on both of these graph families; however, prior to this work, the best possible approximation guarantees for these graphs were wide open. In this paper, we give a tight 2-approximation for BMWIS on perfect graphs and bipartite graphs. In particular, we give a (2 − ɛ) lower bound for BMWIS on bipartite graphs, already for the special case where the budget is replaced by a cardinality constraint, based on the Small Set Expansion Hypothesis (SSEH). For the upper bound, we design a 2-approximation for BMWIS on perfect graphs using a Lagrangian relaxation based technique. Finally, we obtain a tight lower bound for the capacitated maximum weight independent set (CMWIS) problem, the special case of BMWIS where w (v) = c (v) ∀ v ∈ V. We show that CMWIS on bipartite and perfect graphs is unlikely to admit an efficient polynomial-time approximation scheme (EPTAS). Thus, the existing PTAS for CMWIS is essentially the best we can expect. [ABSTRACT FROM AUTHOR]