6 papers
On the Parameterized Tractability of Packing Vertex-Disjoint A-Paths with Length Constraints
Susobhan Bandopadhyay, Aritra Banik, Diptapriyo Majumdar +1
Given an undirected graph G and a set A \subseteq V(G), an A-path is a path in G that starts and ends at two distinct vertices of A with intermediate vertices in V(G) \setminus A.…
Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds
Aritra Banik, Sujoy Bhore, Palash Dey +1
The kidney exchange mechanism allows many patient-donor pairs who are otherwise incompatible with each other to come together and exchange kidneys along a cycle. However, due to in…
Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
Aritra Banik, Mano Prakash Parthasarathi, Venkatesh Raman +2
The Minimum Consistent Subset (MCS) problem arises naturally in the context of supervised clustering and instance selection. In supervised clustering, one aims to infer a meaningfu…
Identifying Codes Kernelization Limitations
Aritra Banik, Praneet Kumar Patra, Adele Anna Rescigno +1
The Identifying Code (IC) problem seeks a vertex subset whose intersection with every vertex's closed neighborhood is unique, enabling fault detection in multiprocessor systems and…
New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
Aritra Banik, Sayani Das, Anil Maheshwari +6
In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph , consisting of a vertex set of size and an edge set .…
Multivariate Exploration of Metric Dilation
Aritra Banik, Fedor V. Fomin, Petr A. Golovach +3
Let be a weighted graph embedded in a metric space . The vertices of correspond to the points in , with the weight of each edge being the distance $d_M…