Seminars

View all Seminars  |  Download ICal for this event

On Computing Homological Hitting Sets

Series: Bangalore Theory Seminars

Speaker: Abhishek Jayantilal Rathod, Purdue University

Date/Time: Feb 02 18:00:00

Location: Microsoft Teams - ON-LINE

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 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 + d, where d is the maximum degree of the Hasse graph of the complex K.
<br>
The talk is based on joint work with Ulrich Bauer and Meirav Zehavi.
<br>
<br>
Microsoft teams link:
<br>
Link
<br>
<br>
We acknowledge the Kirani familys generous support towards conducting this seminar series.
<br>
<br>
Hosts: Aditya Abhay Lonkar, Aditya Subramanian, Rahul Madhavan & Rameesh Paul