Given a graph @math , a non-negative integer @math , and a weight function that maps each vertex in @math to a positive real number, the is about finding a maximum weighted independent set in @math of cardinality at most @math . A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in @math , is called the problem. In other words, the MIVC problem is about finding an independent set of cardinality at most @math with maximum coverage. Since it is a generalization of the well-known Maximum Weighted Independent Set (MWIS) problem, MWBIS too does not have any constant factor polynomial time approximation algorithm assuming @math . In this paper, we study MWBIS in the context of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits a @math -factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation.
A more general problem (also known by the same name, MWBIS,) was introduced and studied in the context of special graphs like trees, forests, cycle graphs, interval graphs, and planar graphs in @cite_9 where each vertex in the given graph @math has a cost associated with it and the problem is about finding an independent set of total cost at most @math (, where @math is a part of the input,) in @math that has the highest weight amongst all such independent sets. Apart from this work, to the best of our knowledge, not much is known about MWBIS.
@cite_9
1863224559
We study a natural extension of the Maximum Weight Independent Set Problem (MWIS), one of the most studied optimization problems in Graph algorithms. We are given a graph @math , a weight function @math , a budget function @math , and a positive integer @math . The weight (resp. budget) of a subset of vertices is the sum of weights (resp. budgets) of the vertices in the subset. A @math -budgeted independent set in @math is a subset of vertices, such that no pair of vertices in that subset are adjacent, and the budget of the subset is at most @math . The goal is to find a @math -budgeted independent set in @math such that its weight is maximum among all the @math -budgeted independent sets in @math . We refer to this problem as MWBIS. Being a generalization of MWIS, MWBIS also has several applications in Scheduling, Wireless networks and so on. Due to the hardness results implied from MWIS, we study the MWBIS problem in several special classes of graphs. We design exact algorithms for trees, forests, cycle graphs, and interval graphs. In unweighted case we design an approximation algorithm for @math -claw free graphs whose approximation ratio ( @math ) is competitive with the approximation ratio ( @math ) of MWIS (unweighted). Furthermore, we extend Baker's technique Baker83 to get a PTAS for MWBIS in planar graphs.