Inapproximability of \(H\)-transversal/packing.

*(English)*Zbl 1371.68099Summary: Given an undirected graph \(G = (V_G, E_G)\) and a fixed “pattern” graph \(H = (V_H, E_H)\) with \(k\) vertices, we consider the \(H\)-Transversal and \(H\)-Packing problems. The former asks to find the smallest \(S \subseteq V_G\) such that the subgraph induced by \(V_G \setminus S\) does not have \(H\) as a subgraph, and the latter asks to find the maximum number of pairwise disjoint \(k\)-subsets \(S_1,\dots, S_m \subseteq V_G\) such that the subgraph induced by each \(S_i\) 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 \(\widetilde \Omega (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.

Reviewer: Reviewer (Berlin)

##### MSC:

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

68W25 | Approximation algorithms |

PDF
BibTeX
XML
Cite

\textit{V. Guruswami} and \textit{E. Lee}, SIAM J. Discrete Math. 31, No. 3, 1552--1571 (2017; Zbl 1371.68099)

Full Text:
DOI

##### References:

[1] | M. Andrews, J. Chuzhoy, V. Guruswami, S. Khanna, K. Talwar, and L. Zhang, Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs, Combinatorica, 30 (2010), pp. 485–520. · Zbl 1240.68113 |

[2] | M. Andrews and L. Zhang, Logarithmic hardness of the undirected edge-disjoint paths problem, J. ACM, 53 (2006), pp. 745–761. · Zbl 1326.68143 |

[3] | P. Austrin, S. Khot, and M. Safra, Inapproximability of vertex cover and independent set in bounded degree graphs, in Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC ’09), 2009, pp. 74–80, . · Zbl 1243.68183 |

[4] | V. Bafna, P. Berman, and T. Fujito, Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs, in Proceedings of the 6th International Symposium on Algorithms and Computation (ISAAC ’95), 1995, pp. 142–151, . |

[5] | N. Bansal and S. Khot, Inapproximability of hypergraph vertex cover and applications to scheduling problems, in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP’ 10), 2010, pp. 250–261, . · Zbl 1287.90018 |

[6] | R. Bar-Yehuda, D. Geiger, J. Naor, and R. Roth, Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and bayesian inference, SIAM J. Comput., 27 (1998), pp. 942–959, . · Zbl 0907.68110 |

[7] | A. Becker and D. Geiger, Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Artificial Intell., 83 (1996), pp. 167–188, . |

[8] | H. L. Bodlaender, On disjoint cycles, Internat. J. Found. Comput. Sci., 5 (1994), pp. 59–68. · Zbl 0803.05030 |

[9] | A. Brandstädt, V. Chepoi, and F. Dragan, Clique r-domination and clique r-packing problems on dually chordal graphs, SIAM J. Discrete Math., 10 (1997), pp. 109–127. · Zbl 0869.05048 |

[10] | P. Chalermsook, B. Laekhanukit, and D. Nanongkai, Pre-reduction graph products: Hardnesses of properly learning DFAs and approximating EDP on DAGs, in Proceedings of Foundations of Computer Science, 2014. |

[11] | S. Chan, Approximation resistance from pairwise independent subgroups, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC ’13), 2013, pp. 447–456, . · Zbl 1293.68163 |

[12] | M.-S. Chang, T. Kloks, and C.-M. Lee, Maximum clique transversals, in Proceedings of Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 2204, 2001, pp. 32–43. · Zbl 1042.68619 |

[13] | F. Chataigner, G. Manic, Y. Wakabayashi, and R. Yuster, Approximation algorithms and hardness results for the clique packing problem, Discrete Appl. Math., 157 (2009), pp. 1396–1406, . · Zbl 1172.05046 |

[14] | J. Chen, Y. Liu, S. Lu, B. O’sullivan, and I. Razgon, A fixed-parameter algorithm for the directed feedback vertex set problem, J. ACM, 55 (2008), pp. 21:1–21:19, . |

[15] | R. Chitnis, M. Cygan, M. Hajiaghayi, and D. Marx, Directed subset feedback vertex set is fixed-parameter tractable, in Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP ’12), 2012, pp. 230–241, . · Zbl 1272.68149 |

[16] | M. Chlebík and J. Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Inform. and Comput., 206 (2008), pp. 1264–1275. |

[17] | F. A. Chudak, M. X. Goemans, D. S. Hochbaum, and D. P. Williamson, A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs, Oper. Res. Lett., 22 (1998), pp. 111–118, . · Zbl 0920.90137 |

[18] | M. Cygan, Improved approximation for 3-dimensional matching via bounded pathwidth local search, in Proceedings of the 54th Annual IEEE symposium on Foundations of Computer Science (FOCS ’13), 2013, pp. 509–518. |

[19] | M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk, Subset feedback vertex set is fixed-parameter tractable, in Proceedings of the 38th International Colloquim on Automata, Languages and Programming (ICALP ’11), 2011, pp. 449–461, . · Zbl 1334.68096 |

[20] | I. Dinur, V. Guruswami, S. Khot, and O. Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, SIAM J. Comput., 34 (2005), pp. 1129–1146. · Zbl 1079.68039 |

[21] | I. Dinur and S. Safra, On the hardness of approximating minimum vertex cover, Ann. Math., 162 (2005), pp. 439–485. · Zbl 1084.68051 |

[22] | D. Dor and M. Tarsi, Graph decomposition is NP-complete: A complete proof of Holyer’s conjecture, SIAM J. Comput., 26 (1997), pp. 1166–1187. · Zbl 0884.05071 |

[23] | G. Durán, M. C. Lin, S. Mera, and J. L. Szwarcfiter, Algorithms for finding clique-transversals of graphs, Ann. Oper. Res., 157 (2008), pp. 37–45. · Zbl 1163.90768 |

[24] | P. Erdös, T. Gallai, and Z. Tuza, Covering the cliques of a graph with vertices, Discrete Math., 108 (1992), pp. 279–289. · Zbl 0766.05063 |

[25] | G. Even, J. Naor, S. Rao, and B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, J. ACM, 47 (2000), pp. 585–616, . · Zbl 1303.68156 |

[26] | G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20 (1998), pp. 151–174. · Zbl 0897.68078 |

[27] | T. Feder and C. Subi, Packing edge-disjoint triangles in given graphs, in Proceedings of the Electronic Colloquium on Computational Complexity (ECCC), TR12-013, 2012. |

[28] | Z. Friggstad and M. R. Salavatipour, Approximability of packing disjoint cycles, in Proceedings of the 18th International conference on Algorithms and Computation (ISAAC’ 07), 2007, pp. 304–315, . · Zbl 1193.68286 |

[29] | V. Guruswami and E. Lee, Inapproximability of feedback vertex set for bounded length cycles, in Proceedings of the Electronic Colloquium on Computational Complexity (ECCC), TR 14-006, 2014. |

[30] | V. Guruswami and E. Lee, Inapproximability of \( H \)-Transversal/Packing, preprint , 2015. |

[31] | V. Guruswami and E. Lee, Inapproximability of H-Transversal/Packing, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz Int. Proc. Inform., 40, 2015, pp. 284–304, . · Zbl 1375.68059 |

[32] | V. Guruswami, R. Manokaran, and P. Raghavendra, Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph, in Proceedings of the 49th annual IEEE symposium on Foundations of Computer Science (FOCS ’08) 2008, pp. 573–582, . |

[33] | V. Guruswami and C. Pandu Rangan, Algorithmic aspects of clique-transversal and clique-independent sets, Discrete Appl. Math., 100 (2000), pp. 183–202, . · Zbl 0948.68135 |

[34] | V. Guruswami, C. Pandu Rangan, M. S. Chang, G. J. Chang, and C. K. Wong, The K\(_r\)-packing problem, Computing, 66 (2001), pp. 79–89, . · Zbl 0978.05060 |

[35] | E. Hazan, S. Safra, and O. Schwartz, On the complexity of approximating k-set packing, Comput. Complexity, 15 (2006), pp. 20–39. · Zbl 1103.90105 |

[36] | P. Hell, S. Klein, L. Nogueira, and F. Protti, Packing r-cliques in weighted chordal graphs, Ann. Oper. Res., 138 (2005), pp. 179–187, . · Zbl 1091.90073 |

[37] | B. M. P. Jansen and D. Marx, Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and turing kernels, in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’15), 2015, pp. 616–629. · Zbl 1371.68212 |

[38] | S. Khot, On the power of unique 2-prover 1-round games, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC ’02), 2002, pp. 767–775, . · Zbl 1192.68367 |

[39] | S. Khot and O. Regev, Vertex cover might be hard to approximate to within \(2-ϵ\), J. Comput. System Sci., 74 (2008), pp. 335–349. · Zbl 1133.68061 |

[40] | D. Kirkpatrick and P. Hell, On the complexity of general graph factor problems, SIAM J. Comput., 12 (1983), pp. 601–609. · Zbl 0525.68023 |

[41] | T. Kloks, Packing Interval Graphs with Vertex-Disjoint Triangles, preprint, , 2012. |

[42] | G. Kortsarz, M. Langberg, and Z. Nutov, Approximating maximum subgraphs without short cycles, SIAM J. Discrete Math., 24 (2010), pp. 255–269. · Zbl 1214.05057 |

[43] | M. Krivelevich, Z. Nutov, M. R. Salavatipour, J. V. Yuster, and R. Yuster, Approximation algorithms and hardness results for cycle packing problems, ACM Trans. Algorithms, 3 (2007), . · Zbl 1297.05127 |

[44] | C. Lee, M. Chang, and S. Sheu, The clique transversal and clique independence of distance hereditary graphs, in Proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 2002, pp. 64–69. |

[45] | C.-M. Lee, Weighted maximum-clique transversal sets of graphs, ISRN Discrete Math., 2011 (2011). · Zbl 1237.05153 |

[46] | E. Lee, Partitioning a graph into small pieces with applications to path transversal, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms SIAM, 2017, pp. 1546–1558. · Zbl 1410.68303 |

[47] | C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, in Automata, Languages and Programming, Lecture Notes in Comput. Sci. 700, 1993, pp. 40–51. |

[48] | S. Rajagopalan and V. V. Vazirani, Primal-dual RNC approximation algorithms for set cover and covering integer programs, SIAM J. Comput., 28 (1998), pp. 525–540. · Zbl 0914.68096 |

[49] | D. Rautenbach and F. Regen, On packing shortest cycles in graphs, Inform. Process. Lett., 109 (2009), pp. 816–821, . · Zbl 1197.05119 |

[50] | P. D. Seymour, Packing directed circuits fractionally, Combinatorica, 15 (1995), pp. 281–288, . · Zbl 0826.05031 |

[51] | E. Shan, Z. Liang, and L. Kang, Clique-transversal sets and clique-coloring in planar graphs, European J. Combin., 36 (2014), pp. 367–376. · Zbl 1284.05075 |

[52] | O. Svensson, Hardness of vertex deletion and project scheduling, Theory Comput., 9 (2013), pp. 759–781, . · Zbl 1366.68083 |

[53] | P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok, 48 (1941), p. 137. |

[54] | Z. Tuza, Covering all cliques of a graph, in Topics on Domination, S. Hedetniemi, ed., Ann. Discrete Math. 48, Elsevier, 1991, pp. 117–126, . · Zbl 0744.05040 |

[55] | R. Yuster, Combinatorial and computational aspects of graph packing and graph decomposition, Comput. Sci. Rev., 1 (2007), pp. 12–26. · Zbl 1302.05149 |

[56] | R. Yuster, Edge-disjoint cliques in graphs with high minimum degree, SIAM J. Discrete Math., 28 (2014), pp. 893–910, . · Zbl 1301.05192 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.