Graph Connectivity, Partitioning, and Fair Allocation: A Parameterized Persp

Instructor : Susobhan Bandopadhyay
Affiliation : NISER Bhubaneswar
Abstract : This talk focuses on Graph Connectivity, Partitioning, and their relation to the Fair Allocation problem in the parameterized complexity framework. We study the (A,ℓ)-Path Packing problem, a variant of Graph Connectivity, 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 analogous to the 'Isolation Lemma' and could aid in proving hardness for related problems. We also explore the Shortest Non-Separating Path problem, which aims to find a path between two vertices such that removing the path’s vertices does not disrupt overall graph connectivity. This is equivalent to partitioning the vertex set into two parts: one forming the shortest path and the other inducing a connected component. We show that the 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.

Furthermore, we study the Constrained k-way Cut problem, which generalizes the π-Deletion and k-way Cut problems. Here, the objective is to delete edges to partition the graph into exactly k components, each conforming to a specific graph family π such as trees, bipartite, chordal, and bounded-degree.

Finally, we extend the study of the Fair Allocation problem to incorporate conflicts among resources, modeled by a conflict graph, where resources assigned to an agent maximize agent welfare and induce an independent 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.

Short Bio: Mr. Susobhan Bandopadhyay completed his B.Sc. from Ramakrishna MissionVidyamandira, Belur Math, Howrah, followed by an M.Sc. in Computer Science from Ramakrishna Mission Vivekananda Educational and Research Institute, Belur Math, Howrah. Presently, he is pursuing Ph.D. at NISER Bhubaneswar under the guidance of Dr. Aritra Banik. His current research focuses on parameterized algorithms, graph algorithms, and social choice theory.