Approximations via partitioning
Magnús M. Halldórsson · 1995
We consider the approximation of weighted maximum subgraph problems by partitioning the input graph into easier subproblems. In particular, we obtain efficient approximations of the weighted independent set problem with performance ratios of O(n(log log n / log n) 2) and ( ∆ + 2)/3, with the latter improving on a ∆/2 ratio of Hochbaum for ∆ ≥ 5. We also obtain a O(n / log n) performance ratio for various maximization problems where a subset of a solution is also a solution. 1 Partitioning and hereditary induced subgraph problems A property of graphs is hereditary if whenever it holds for a graph it also holds for its induced subgraphs. For a hereditary property, the associated subgraph problem is that of finding a subgraph of maximum weight satisfying the property. We say that a problem is approximable within f(n) if there is a polynomial time algorithm that on graphs with n vertices returns a feasible solution within f(n) factor of optimal. Hereditary can be generalized to other discrete structures. A property is hereditary if whenever it holds for a subset X of the instance, it also holds for any subset of X.