2026-07-23T06:52:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5308 2024-03-06T10:36:17Z ddc:004 open_access

Inapproximability of H-Transversal/Packing Guruswami, Venkatesan Lee, Euiwoong Constraint Satisfaction Problems Approximation resistance 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Venkatesan Guruswami and Euiwoong Lee 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.284 urn:nbn:de:0030-drops-53085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.284 eng https://creativecommons.org/licenses/by/3.0/legalcode