BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1486
DTSTAMP:20241017T052217Z
SUMMARY:Graph Connectivity\, Partitioning\, and Fair Allocation: A Paramete
 rized Perspective
DESCRIPTION:Speaker: Susobhan Bandopadhyay (NISER Bhubaneswar)\n\nAbstract:
  \nThis talk focuses on Graph Connectivity\, Partitioning\, and their rel
 ation to the Fair Allocation problem in the parameterized complexity fram
 ework. We study the (A\,ℓ)-Path Packing problem\, a variant of Graph Co
 nnectivity\, where the goal is to maximize the number of vertex-disjoint 
 paths of length ℓ\, connecting disjoint pairs from the vertex subset A.
  Our work improves upon the hardness result established by Belmonte et al
 . [Algorithmica\, '22]\, introducing a 'Separation Lemma’\, which is an
 alogous to the 'Isolation Lemma' and could aid in proving hardness for re
 lated problems. We also explore the Shortest Non-Separating Path problem\
 , which aims to find a path between two vertices such that removing the p
 ath’s vertices does not disrupt overall graph connectivity. This is eq
 uivalent to partitioning the vertex set into two parts: one forming the s
 hortest path and the other inducing a connected component. We show that t
 he problem is intractable when parameterized by path length. In contrast\
 , its edge-based variant\, the Shortest Non-Disconnecting Path problem\, 
 is fixed-parameter tractable using matroid-based techniques.\nFurthermore
 \, we study the Constrained k-way Cut problem\, which generalizes the π-D
 eletion and k-way Cut problems. Here\, the objective is to delete edges to
  partition the graph into exactly k components\, each conforming to a spec
 ific graph family π such as trees\, bipartite\, chordal\, and bounded-deg
 ree.\nFinally\, we extend the study of the Fair Allocation problem to inco
 rporate conflicts among resources\, modeled by a conflict graph\, where re
 sources assigned to an agent maximize agent welfare and induce an independ
 ent set. This formulation is closely related to the Constrained k-way Cut 
 problem but shifts the focus from minimizing edge deletions to maximizing 
 agent welfare. Our parameterized analysis yields various tractability and 
 intractability results.\nShort Bio: Mr. Susobhan Bandopadhyay completed hi
 s B.Sc. from Ramakrishna MissionVidyamandira\, Belur Math\, Howrah\, follo
 wed by an M.Sc. in Computer Science from Ramakrishna Mission Vivekananda E
 ducational and Research Institute\, Belur Math\, Howrah. Presently\, he is
  pursuing Ph.D. at NISER Bhubaneswar under the guidance of Dr. Aritra Bani
 k. His current research focuses on parameterized algorithms\, graph algori
 thms\, and social choice theory.\n
URL:https://www.tcs.tifr.res.in/web/events/1486
DTSTART;TZID=Asia/Kolkata:20241025T160000
DTEND;TZID=Asia/Kolkata:20241025T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR