License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.13
URN: urn:nbn:de:0030-drops-175169
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17516/
Bauer, Ulrich ;
Rathod, Abhishek ;
Zehavi, Meirav
On Computing Homological Hitting Sets
Abstract
Cut problems form one of the most fundamental classes of problems in algorithmic graph theory. In this paper, we initiate the algorithmic study of a high-dimensional cut problem. The problem we study, namely, Homological Hitting Set (HHS), is defined as follows: Given a nontrivial r-cycle z in a simplicial complex, find a set ? of r-dimensional simplices of minimum cardinality so that ? meets every cycle homologous to z. Our first result is that HHS admits a polynomial-time solution on triangulations of closed surfaces. Interestingly, the minimal solution is given in terms of the cocycles of the surface. Next, we provide an example of a 2-complex for which the (unique) minimal hitting set is not a cocycle. Furthermore, for general complexes, we show that HHS is W[1]-hard with respect to the solution size p. In contrast, on the positive side, we show that HHS admits an FPT algorithm with respect to p+Δ, where Δ is the maximum degree of the Hasse graph of the complex ?.
BibTeX - Entry
@InProceedings{bauer_et_al:LIPIcs.ITCS.2023.13,
author = {Bauer, Ulrich and Rathod, Abhishek and Zehavi, Meirav},
title = {{On Computing Homological Hitting Sets}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {13:1--13:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17516},
URN = {urn:nbn:de:0030-drops-175169},
doi = {10.4230/LIPIcs.ITCS.2023.13},
annote = {Keywords: Algorithmic topology, Cut problems, Surfaces, Parameterized complexity}
}
Keywords: |
|
Algorithmic topology, Cut problems, Surfaces, Parameterized complexity |
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
01.02.2023 |