Author name cluster

Aritra Banik

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Kidney Exchange: Faster Parameterized Algorithms and Tighter Lower Bounds

Palash Dey
Aritra Banik
Abhishek Sahu
Sujoy Bhore

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 infrastructure and legal constraints, kidney exchange can only be performed in small cycles in practice. In reality, there are also some altruistic donors who do not have any paired patients. This allows us to also performkidneyexchangealongpathsthatstartfromsomealtruistic donor. Unfortunately, the computational task is NP-complete. To overcome this computational barrier, an important line of research focuses on designing faster algorithms, both exact and using the framework of parameterized complexity. The standard parameter for the kidney exchange problem is the number 𝑡 of patients that receive a healthy kidney. The current fastest known deterministic FPT algorithm for this problem, parameterized by 𝑡, is O★ 14𝑡. In this work, we improve this by presenting a deterministic FPT algorithm that runs in time O★ (4𝑒)𝑡 ≈ O★ 10. 88𝑡. This problem is also known to be W[1]hard parameterized by the treewidth of the underlying undirected graph. A natural question here is whether the kidney exchange problem admits an FPT algorithm parameterized by the pathwidth of the underlying undirected graph. We answer this negatively in this paper by proving that this problem is W[1]-hard parameterized by the pathwidth of the underlying undirected graph. We also present some parameterized intractability results improving the current understanding of the problem under the framework of parameterized complexity.

PDF

AAAI Conference 2026 Conference Paper

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs

Aritra Banik
Mano Prakash Parthasarathi
Venkatesh Raman
Diya Roy
Abhishek Sahu

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 meaningful partitioning of data using a small labeled subset. However, the sheer volume of training data in modern applications poses a significant computational challenge. The MCS problem formalizes this goal: given a labeled dataset X in a metric space, the task is to compute a smallest subset S of X such that every point in X shares its label with at least one of its nearest neighbors in S. Recently, the MCS problem has been extended to graph metrics, where distances are defined by shortest paths. Prior work has shown that MCS remains NP-hard even on simple graph classes like trees, and presented an fixed-parameter tractable (FPT) algorithm parameterized by the number of colors for MCS on trees. This raises the challenge of identifying graph classes that admit algorithms efficient in both input size (n) and the number of colors (c). In this work, we study the Minimum Consistent Subset problem on graphs, focusing on two well-established measures: the vertex cover number (vc) and the neighborhood diversity (nd). Specifically, we design efficient algorithms for graphs exhibiting small vc or small nd, which frequently arise in real-world domains characterized by local sparsity or repetitive structure. These parameters are particularly relevant because they capture structural properties that often correlate with the tractability of otherwise hard problems. Graphs with small vertex cover sizes are "almost independent sets", representing sparse interactions, while graphs with small neighborhood diversity exhibit a high degree of symmetry and regularity. Importantly, small neighborhood diversity can occur even in dense graphs, a property frequently observed in domains such as social networks with modular communities or knowledge graphs with repeated relational patterns. Thus, algorithms designed to work efficiently for graphs with small neighborhood diversity are capable of efficiently solving MCS in complex settings where small vertex covers may not exist. We show that MCS is FPT when parameterized by the vertex cover number and by neighborhood diversity. In each case, we present an algorithm whose running time is polynomial in n and c, and the non-polynomial part depends solely on the chosen parameter. Notably, our algorithms remain efficient for arbitrarily many colors, as their complexity is polynomially dependent on the number of colors.

PDF Details DOI

MFCS Conference 2024 Conference Paper

Tractability of Packing Vertex-Disjoint A-Paths Under Length Constraints

Susobhan Bandopadhyay
Aritra Banik
Diptapriyo Majumdar
Abhishek Sahu

Given an undirected graph G and a set A ⊆ 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)⧵A. An A-path is called an (A, 𝓁)-path if the length of the path is exactly 𝓁. In the (A, 𝓁)-Path Packing problem (ALPP), we seek to determine whether there exist k vertex-disjoint (A, 𝓁)-paths in G or not. The problem is already known to be fixed-parmeter tractable when parameterized by k+𝓁 via color coding while it remains Para-NP-hard when parameterized by k (Hamiltonian Path) or 𝓁 (P₃-Partition) alone. Therefore, a logical direction to pursue this problem is to examine it in relation to structural parameters. Belmonte et al. initiated a study along these lines and proved that ALPP parameterized by pw+|A| is W[1]-hard where pw is the pathwidth of G. In this paper, we strengthen their result and prove that it is unlikely that ALPP is fixed-parameter tractable even with respect to a bigger parameter (|A|+dtp) where dtp denotes the distance between G and a path graph (distance to path). We use a randomized reduction to achieve the mentioned result. Toward this, we prove a lemma similar to the influential "isolation lemma": Given a set system (X, ℱ) if the elements of X are assigned a weight uniformly at random from a set of values fairly large, then each subset in ℱ will have a unique weight with high probability. We believe that this result will be useful beyond the scope of this paper. ALPP being hard even for structural parameters like distance to path+|A| rules out the possibility of any FPT algorithms for many well-known other structural parameters, including FVS+|A| and treewidth+|A|. There is a straightforward FPT algorithm for ALPP parameterized by vc, the vertex cover number of the input graph. Following this, we consider the parameters CVD(cluster vertex deletion)+|A| and CVD+|𝓁| and show the problem to be FPT with respect to these parameters. Note that CVD is incomparable to the treewidth of a graph and has been in vogue recently.

Details

TCS Journal 2023 Journal Article

Parameterized algorithms for finding highly connected solution

Ankit Abhinav
Susobhan Bandopadhyay
Aritra Banik
Saket Saurabh

To introduce our question and the parameterization, consider the classical Vertex Cover problem. In this problem, the input is a graph G on n vertices and a positive integer ℓ, and the goal is to find a vertex subset S of size at most ℓ such that G − S is an independent set. Further, we want that G [ S ] is highly connected. That is, G [ S ] should be n − k edge-connected. Clearly, the problem is NP-complete, as substituting k = n − 1, we obtain the Connected Vertex Cover problem. A simple observation also shows that the problem admits an algorithm with running time n O ( k ). Since the problem is polynomial-time solvable for every fixed integer k, a natural parameter is the integer k. In all the problems we consider, the parameter is k, and the goal is to find a solution S of size at most ℓ, such that G [ S ] is n − k edge-connected and G − S satisfies a property. We show that this version of well-known problems such as Vertex Cover, Feedback Vertex Set, Odd Cycle Transversal and Multiway Cut admit an algorithm with running time f ( k ) ⋅ n O ( 1 ), that is, they are FPT with the parameter k. One of our main subroutines to obtain these algorithms is an FPT algorithm for n − k edge connected Steiner Subgraph, which could be of an independent interest. Finally, we also show that such an algorithm is not possible for Multicut.

Details DOI

TCS Journal 2023 Journal Article

Structural parameterizations of budgeted graph coloring

Susobhan Bandopadhyay
Suman Banerjee
Aritra Banik
Venkatesh Raman

We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (BCP). Given a graph G, an integer c and an ordered list of integers ( b 1, b 2, …, b c ), BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most b i many vertices. This problem generalizes two well-studied graph coloring problems, Bounded Coloring Problem (BoCP) and Equitable Coloring Problem (ECP) and as in the case of other coloring problems, the BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph class. • We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not known. • We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same parameter. • While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. As BoCP is hard on bipartite graphs when c > 3, the result follows for BCP as well. We provide a dichotomy result by showing that BCP is polynomial time solvable on bipartite graphs when c = 2. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and BoCP. Finally we present an O ⁎ ( 2 | V ( G ) | ) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.

Details DOI

MFCS Conference 2022 Conference Paper

Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

Ankit Abhinav
Susobhan Bandopadhyay
Aritra Banik
Yasuaki Kobayashi
Shunsuke Nagano
Yota Otachi
Saket Saurabh 0001

For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.

Details

TCS Journal 2021 Journal Article

Geometric planar networks on bichromatic collinear points

Sayan Bandyapadhyay
Aritra Banik
Sujoy Bhore
Martin Nöllenburg

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP -hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting.

Details DOI

TCS Journal 2021 Journal Article

Voronoi game on polygons

Aritra Banik
Arun Kumar Das
Sandip Das
Anil Maheshwari
Sarvottamananda

The competitive facility location problem is the problem of determining facility locations involving multiple players to optimize their various gains. The Voronoi game is a competitive facility location problem on a given arena played by two players, the server and the adversary. The players alternately take turns, one or more times, to place their facilities in the arena with a predetermined set of n clients, where both facilities and clients are denoted by points, to maximize some resource gain. The Voronoi game on a polygon P is a type of competitive facility location problem where n clients are located on the boundary of P. The server, Alice, and adversary, Bob, are respectively in the interior and the exterior of the polygon P at locations A and B, respectively. Additionally, the metrics for Alice and Bob are the internal and external geodesic distances for the polygon P, respectively. In this paper, we present some surprising results on the Voronoi games on polygons. We prove lower and upper bounds of ⌈ n / 3 ⌉ and n − 1 respectively in the single-round game for the number of clients won by the server for n clients. Both bounds are tight. In the process, we show that in some convex polygons, the adversary wins no more than k clients in a k-round Voronoi game for any k ≤ n. Consequentially, the adversary Bob does not have a guaranteed good winning strategy even for the simpler case of convex polygons, i. e. , there exist convex polygons such that no placement of B guarantees more than k clients in the k-round game. We also design O ( n log 2 ⁡ n + m log ⁡ n ) and O ( n + m ) time algorithms to compute the optimal locations for the server and the adversary respectively to maximize their client counts where the convex polygon has size m. Moreover, we present an O ( n log ⁡ n ) time algorithm to compute the common intersection of a set of n ellipses. This is needed in our algorithm and may be of independent interest. Lastly, we present some results on the Voronoi games, where the arena is a convex polytope. The server and adversary are respectively in the interior and exterior of P, and the clients are on the polytope boundary.

Details DOI

TCS Journal 2020 Journal Article

Fixed-parameter tractable algorithms for Tracking Shortest Paths

Aritra Banik
Pratibha Choudhary
Venkatesh Raman
Saket Saurabh

We consider the parameterized complexity of the problem of tracking shortest s-t paths in graphs, motivated by applications in security and wireless networks. Given an undirected and unweighted graph with a source s and a destination t, Tracking Shortest Paths asks if there exists a k-sized subset of vertices (referred to as tracking set) that intersects each shortest s-t path in a distinct set of vertices. We first generalize this problem for set systems, namely Tracking Set System, where given a family of subsets of a universe, we are required to find a subset of elements from the universe that has a unique intersection with each set in the family. Tracking Set System is shown to be fixed-parameter tractable due to its relation with a known problem, Test Cover. By a reduction to the well-studied d-hitting set problem, we give a polynomial (with respect to k) kernel for the case when the set sizes are bounded by d. This also helps in solving Tracking Shortest Paths when the input graph diameter is bounded by d. While the results for Tracking Set System show that Tracking Shortest Paths is fixed-parameter tractable, we also give an independent algorithm by using some preprocessing rules, resulting in an improved running time.

Details DOI

TCS Journal 2020 Journal Article

List-coloring – Parameterizing from triviality

Pranav Arora
Aritra Banik
Vijay Kumar Paliwal
Venkatesh Raman

The classical graph coloring problem is given an undirected graph and the goal is to color the vertices of the graph with the minimum number of colors so that endpoints of each edge gets different colors. In list-coloring, each vertex is given a list of allowed colors with which it can be colored. Most versions of the problems are hard in several paradigms including approximation and parameterized complexity. We consider a few versions of the problems that are polynomial time solvable and try to extend the notion of feasible algorithms by parameterizing suitably in the paradigm of parameterized complexity. In particular, we provide extensions of these polynomial time solvable coloring problems that belong to the extreme ends of the parameterized complexity hierarchy including fixed-parameter tractable (FPT) class or the complexity class XP or W [ 1 ] -hard or para-NP -hard (i. e. NP -hard even for constant values of the parameter). Specifically, we consider generalizations of odd cycle transversal and edge bipartization in the context of list-coloring and show them fixed-parameter tractable. We also look at list coloring where each list has n − k colors and the goal is to color the vertices respecting the list. We show that the problem is in the parameterized complexity class XP, when parameterized by k.

Details DOI

TCS Journal 2019 Journal Article

The discrete Voronoi game in a simple polygon

Aritra Banik
Sandip Das
Anil Maheshwari
Michiel Smid

In this paper we consider a competitive facility location problem played between two players P 1 and P 2. Let P be a simple polygon with m vertices. Consider a set of users, U modeled as points in the interior (excluding the boundary) of P. Initially P 1 chooses a point inside P (including the boundary) to place a facility. Following this P 2 chooses another point inside P and places a facility. Given these facilities a user u ∈ U is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by P 1, an optimal placement for P 2 can be computed in O ( m + n ( log ⁡ n + log ⁡ m ) ) time. We also provide a polynomial-time algorithm for computing an optimal placement for P 1.

Details DOI

TCS Journal 2015 Journal Article

Voronoi game on graphs

Sayan Bandyapadhyay
Aritra Banik
Sandip Das
Hirak Sarkar

Voronoi game is a geometric model of competitive facility location problem played between two players. Users are generally modeled as points uniformly distributed on a given underlying space. Each player chooses a set of points in the underlying space to place their facilities. Each user avails service from its nearest facility. Service zone of a facility consists of the set of users which are closer to it than any other facility. Payoff of each player is defined by the quantity of users served by all of its facilities. The objective of each player is to maximize their respective payoff. In this paper we consider the two player Voronoi game where the underlying space is a road network modeled by a graph. In this framework we consider the problem of finding k optimal facility locations of Player 2 given any placement of m facilities by Player 1. Our main result is a dynamic programming based polynomial time algorithm for this problem on tree network. On the other hand, we show that the problem is strongly NP -complete for graphs. This proves that finding a winning strategy of P2 is NP -complete. Consequently, we design a 1 − 1 e factor approximation algorithm, where e ≈ 2. 718.

Details DOI