Approximating node-deletion problems for matroidal properties

The paper is concerned with the polynomial time approximability of node-del etion 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 con sider two well-known approaches, greedy and primal-dual. The heuristics bas ed on these principles are analyzed and general approximation bounds are ob tained. Next, more specific typos of hereditary properties, called uniforml y sparse, are introduced and, for any of them, the primal-dual heuristic is shown to approximate the corresponding node-deletion problem within a fact or of 2. We conclude that there exist infinitely many (at least countably m any) node-deletion problems, each of which approximable to a factor of 2, f or hereditary properties with an infinite number of minimal forbidden graph s. (C) 1999 Academic Press.