Hitting Meets Packing: How Hard Can It Be?

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.