CISPA
Browse
2402.14927v1.pdf (1.58 MB)

Hitting Meets Packing: How Hard Can it Be?

Download (1.58 MB)
preprint
posted on 2024-03-01, 08:05 authored by Jacob FockeJacob Focke, Fabian FreiFabian Frei, Shaohua Li, Dániel MarxDániel Marx, Philipp SchepperPhilipp Schepper, Roohani Sharma, Karol Węgrzycki
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 X-HitPack asks: Can removing k (deletable) vertices of a graph G prevent us from packing $\ell$ vertex-disjoint objects of type X? This problem captures a spectrum of problems with standard hitting and packing on opposite ends. Our main motivating question is whether the combination X-HitPack can be significantly harder than these two base problems. Already for a particular choice of X, this question can be posed for many different complexity notions, leading to a large, so-far unexplored domain in the intersection of the areas of hitting and packing problems. On 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+l 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 with 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 example, for X being all cycles, we establish a 2^poly(k+l)n^O(1) algorithm using an involved branching method. 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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{Focke:Frei:Li:Marx:Schepper:Sharma:Węgrzycki:2024, title = "Hitting Meets Packing: How Hard Can it Be?", author = "Focke, Jacob" AND "Frei, Fabian" AND "Li, Shaohua" AND "Marx, Dániel" AND "Schepper, Philipp" AND "Sharma, Roohani" AND "Węgrzycki, Karol", year = 2024, month = 2 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC