2026-07-22T05:41:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17516 2024-03-06T10:59:47Z ddc:004 open_access

On Computing Homological Hitting Sets Bauer, Ulrich Rathod, Abhishek Zehavi, Meirav Algorithmic topology Cut problems Surfaces Parameterized complexity 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 𝖪. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ulrich Bauer and Abhishek Rathod and Meirav Zehavi 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.13 urn:nbn:de:0030-drops-175169 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.13 eng https://creativecommons.org/licenses/by/4.0/legalcode