BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230202T120000Z
UID:70dc506294cbc8ce335a7667551c6db1-403
DTSTAMP:19700101T120018Z
DESCRIPTION:On Computing Homological Hitting Sets
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/403/on-computing-homological-hitting-sets/
SUMMARY: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>
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
<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
DTSTART:20230202T120000Z
END:VEVENT
END:VCALENDAR