Hitting Meets Packing: How Hard Can It Be?

Summary

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.