Approximating Element-Weighted Vertex Deletion Problems for the Complete k-Partite Property
✍ Scribed by Reuven Bar-Yehuda; Dror Rawitz
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 143 KB
- Volume
- 42
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
A k-partite graph is a graph G s V , . . . , V , E , where V , . . . , V are k non-
We discuss three variants of the following optimization i / j i j problem: given a graph and a non-negative weight function on the vertices and edges, find a minimum weight set of vertices and incident edges whose removal from the graph leaves a complete k-partite graph. All the problems we consider are at least as hard to approximate as the weighted ¨ertex co¨er problem. We use the local-ratio technique to develop 2-approximation algorithms for the Ž . first two variants of the problem. In particular, we present the first linear time 2-approximation algorithm for the edge clique complement problem. For other previously studied special cases our 2-approximation algorithms are better in terms of time complexity than the existing 2-approximation algorithms. We use approxi-Ž . mation preserving reductions in order to 4 y 4rk -approximate the third variant of the problem.