Hitting Meets Packing: How Hard Can It Be?

At a high level, we present two case studies: (1) X being all cycles, and (2) X 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+\ell 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 Sigma_2^P-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 X being all cycles, we establish a 2^poly(k+\ell) • n^O(1) algorithm using an involved branching method, for example. Also, for X being all edges (i.e., H = K_2; this combines Vertex Cover and Maximum Matching) the problem can be solved in time 2^poly(tw) • n^O(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.

Joint work with Jacob Focke, Fabian Frei, Shaohua Li, Dániel Marx, Roohani Sharma and Karol Węgrzycki.