CISPA
Browse

Hitting Meets Packing: How Hard Can It Be?

Download (1.05 MB)
conference contribution
posted on 2024-10-08, 08:24 authored by Jacob Focke, Fabian FreiFabian Frei, Shaohua Li, DΓ‘niel MarxDΓ‘niel Marx, Philipp Schepper, Roohani Sharma, Karol W\kegrzycki
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.

History

Editor

Chan T ; Fischer J ; Iacono J ; Herman G

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

European Symposium on Algorithms (ESA)

Journal

32nd Annual European Symposium on Algorithms (ESA 2024)

Volume

308

Page Range

55:1-55:21

Publisher

Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik

BibTeX

@inproceedings{Focke:Frei:Li:Marx:Schepper:Sharma:W\kegrzycki: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\kegrzycki, Karol", editor = "Chan, Timothy" AND "Fischer, Johannes" AND "Iacono, John" AND "Herman, Grzegorz", year = 2024, month = 9, journal = "32nd Annual European Symposium on Algorithms (ESA 2024)", pages = "55:1--55:21", publisher = "Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik", issn = "1868-8969", doi = "10.4230/LIPIcs.ESA.2024.55" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC