License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.284
URN: urn:nbn:de:0030-drops-53085
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5308/
Guruswami, Venkatesan ;
Lee, Euiwoong
Inapproximability of H-Transversal/Packing
Abstract
Given an undirected graph G=(V,E) and a fixed pattern graph H with k vertices, we consider the H-Transversal and H-Packing problems. The former asks to find the smallest subset S of vertices such that the subgraph induced by V - S does not have H as a subgraph, and the latter asks to find the maximum number of pairwise disjoint k-subsets S1, ..., Sm such 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 Omega(k) and Omega(k / polylog(k)) respectively. We also show that there is a 1-connected H where H-Transversal admits an O(log k)-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.
BibTeX - Entry
@InProceedings{guruswami_et_al:LIPIcs:2015:5308,
author = {Venkatesan Guruswami and Euiwoong Lee},
title = {{Inapproximability of H-Transversal/Packing}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {284--304},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-89-7},
ISSN = {1868-8969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5308},
URN = {urn:nbn:de:0030-drops-53085},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.284},
annote = {Keywords: Constraint Satisfaction Problems, Approximation resistance}
}
Keywords: |
|
Constraint Satisfaction Problems, Approximation resistance |
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) |
Issue Date: |
|
2015 |
Date of publication: |
|
13.08.2015 |