𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating Node-Deletion Problems for Matroidal Properties

✍ Scribed by Toshihiro Fujito

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
134 KB
Volume
31
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

The paper is concerned with the polynomial time approximability of node-deletion problems for hereditary properties. It is observed that, when such a property derives a matroid on any graph, the problem can be formulated as a matroid set cover optimization problem, and this leads us naturally to consider two well-known approaches, greedy and primal-dual. The heuristics based on these principles are analyzed and general approximation bounds are obtained. Next, more specific types of hereditary properties, called uniformly sparse, are introduced and, for any of them, the primal-dual heuristic is shown to approximate the corresponding nodedeletion problem within a factor of 2. We conclude that there exist infinitely many Ε½ . at least countably many node-deletion problems, each of which approximable to a factor of 2, for hereditary properties with an infinite number of minimal forbidden graphs.

πŸ“œ SIMILAR VOLUMES

Approximating Element-Weighted Vertex De
Approximating Element-Weighted Vertex Deletion Problems for the Complete k-Partite Property
✍ Reuven Bar-Yehuda; Dror Rawitz πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 143 KB

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 r