A ρ-independent set S in a graph is parameterized by a set ρ of non-negative integers that constrains how the independent set S can dominate the remaining vertices (∀v∉S: |N(v)∩S|∈ρ.) For all values of ρ, we classify as either NP-complete or polynomial-time solvable the problems of deciding if a given graph has a ρ-independent set. We complement this with approximation algorithms and inapproximability results, for all the corresponding optimization problems. These approximation results extend also to several related independence problems. In particular, we obtain a m approximation of the Set Packing problem, where m is the number of base elements, as well as a n approximation of the maximum independent set in power graphs Gt, for t even.
|Fræðitímarit||Discrete Applied Mathematics|
|Útgáfustaða||Útgefið - 1 feb. 2000|
|Viðburður||Proceedings of the 1997 5th Twente Workshop on Graphs and Combinatorial Optimization - Enschede, Holland|
Tímalengd: 20 maí 1997 → 22 maí 1997