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 is an element of V has a weight w(v) and a cost c(v), and a budget B. The goal is to find an independent set S subset of V in G such that & sum;(v is an element of S )c(v) <= B, which maximizes the total weight & sum;(v is an element of 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, 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 - 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) for all v is an element of 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. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.