2023/07/17 by Ilan Doron-Arad, Doron-Arad, Ilan, Hadas Shachnai +1 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2307.08592
openalex publication_date 2023/07/17 · openalex created_date 2023/07/19 · openalex updated_date 2026/07/28
We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph G = (V,E), a weight function w:V → ℝ≥ 0, a cost function c:V → ℝ≥ 0, and a budget B ∈ ℝ≥ 0. 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, 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-ε) 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.