Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs

Abstract

We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph $G=(V,E)$, a weight function $w:V\to {\mathbb{R}}_{\ge 0}$, a cost function $c:V\to {\mathbb{R}}_{\ge 0}$, and a budget $B\in {\mathbb{R}}_{\ge 0}$. The goal is to find an independent set $S\subseteq V$ in $G$ such that ${\sum }_{v\in S}c(v)\le B$, which maximizes the total weight ${\sum }_{v\in S}w(v)$. Since the problem on general graphs cannot be approximated within ratio $|V{|}^{1-\epsilon }$ for any $\epsilon >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, the best possible approximation guarantees for these graphs are wide open. In this paper, we give a tight $2$-approximation for BMWIS on perfect graphs and bipartite graphs. In particular, we give We a $(2-\epsilon )$ 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)\forall v\in 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.