2026-07-27T03:51:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21126 2024-09-23T09:13:17Z ddc:004 open_access

Hitting Meets Packing: How Hard Can It Be? Focke, Jacob Frei, Fabian Li, Shaohua Marx, Dániel Schepper, Philipp Sharma, Roohani Węgrzycki, Karol Hitting Packing Covering Parameterized Algorithms Lower Bounds Treewidth We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of 𝒳-HitPack asks: Can removing k (deletable) vertices of a graph G prevent us from packing 𝓁 vertex-disjoint objects of type 𝒳? This problem captures a spectrum of problems with standard hitting and packing on opposite ends. Our main motivating question is whether the combination 𝒳-HitPack can be significantly harder than these two base problems. Already for one particular choice of 𝒳, this question can be posed for many different complexity notions, leading to a large, so-far unexplored domain at the intersection of the areas of hitting and packing problems. At a high level, we present two case studies: (1) 𝒳 being all cycles, and (2) 𝒳 being all copies of a fixed graph H. In each, we explore the classical complexity as well as the parameterized complexity with the natural parameters k+𝓁 and treewidth. We observe that the combined problem can be drastically harder than the base problems: for cycles or for H being a connected graph on at least 3 vertices, the problem is Σ₂^𝖯-complete and requires double-exponential dependence on the treewidth of the graph (assuming the Exponential-Time Hypothesis). In contrast, the combined problem admits qualitatively similar running times as the base problems in some cases, although significant novel ideas are required. For 𝒳 being all cycles, we establish a 2^{poly(k+𝓁)}⋅ n^{𝒪(1)} algorithm using an involved branching method, for example. Also, for 𝒳 being all edges (i.e., H = K₂; this combines Vertex Cover and Maximum Matching) the problem can be solved in time 2^{poly(tw)}⋅ n^{𝒪(1)} on graphs of treewidth tw. The key step enabling this running time relies on a combinatorial bound obtained from an algebraic (linear delta-matroid) representation of possible matchings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Focke and Fabian Frei and Shaohua Li and Dániel Marx and Philipp Schepper and Roohani Sharma and Karol Węgrzycki 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.55 urn:nbn:de:0030-drops-211261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.55 eng https://creativecommons.org/licenses/by/4.0/legalcode