TY - GEN
T1 - On Computing Homological Hitting Sets
AU - Bauer, Ulrich
AU - Rathod, Abhishek
AU - Zehavi, Meirav
N1 - Publisher Copyright:
© Ulrich Bauer, Abhishek Rathod, and Meirav Zehavi; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - 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 S of r-dimensional simplices of minimum cardinality so that S 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 K.
AB - 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 S of r-dimensional simplices of minimum cardinality so that S 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 K.
KW - Algorithmic topology
KW - Cut problems
KW - Parameterized complexity
KW - Surfaces
UR - http://www.scopus.com/inward/record.url?scp=85147539612&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2023.13
DO - 10.4230/LIPIcs.ITCS.2023.13
M3 - Conference contribution
AN - SCOPUS:85147539612
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Yael Tauman
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Y2 - 10 January 2023 through 13 January 2023
ER -