file.pdf (794.73 kB)
Download file

Inapproximability of H-Transversal/Packing

Download (794.73 kB)
journal contribution
posted on 01.11.1991, 00:00 authored by Venkatesan Guruswami, Euiwoong Lee

Given an undirected graph G=(VG,EG) and a fixed "pattern" graph H=(VH,EH) with kvertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest S⊆VG such that the subgraph induced by VG∖S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1,...,Sm⊆VGsuch that the subgraph induced by each Si has H as a subgraph.
We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it is NP-hard to approximate them within a factor of Ω(k) and Ω˜(k) respectively. We also show that there is a 1-connected H where H-Transversal admits an O(logk)-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of H-Transversal where H is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem, and give a different hardness proof for directed graphs.




Usage metrics