Suman Banerjee

I&C Journal 2026 Journal Article

On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints

• Susobhan Bandopadhyay
• Suman Banerjee
• Diptapriyo Majumdar
• Fahad Panolan

We study the Shortest Path problem subject to positive binary disjunctive constraints. In positive disjunctive constraints, there are certain pairs of edges such that at least one edge from every pair must be part of every feasible solution. We initiate the study of Shortest Path with binary positive disjunctive constraints in the perspective of parameterized complexity. Formally, the input instance is a simple undirected graph G = ( V, E ), a forcing graph G f = ( E, E ′ ), two vertices s, t ∈ V(G) and an integer k. Note that the vertex set of Gf is the same as the edge set of G. The goal is to find a set S of at most k edges from G such that there is a path from s to t in the subgraph G = ( V, S ) and S is a vertex cover in Gf. In this paper, we consider two different natural parameterizations for this problem. One natural parameter is the solution size, i. e. k which provides polynomial kernelization results. The other natural parameter is structural parameterizations of Gf, i. e. the size of a modulator X ⊆ E ( G ) = V ( G f ) such that G f − X belongs to some hereditary graph class. We discuss the parameterized complexity of this problem under some structural parameterizations.

TMLR Journal 2025 Journal Article

Buffer-based Gradient Projection for Continual Federated Learning

• Shenghong Dai
• Jy-yong Sohn
• Yicong Chen
• S M Iftekharul Alam
• Ravikumar Balakrishnan
• Suman Banerjee
• Nageen Himayat
• Kangwook Lee

Continual Federated Learning (CFL) is essential for enabling real-world applications where multiple decentralized clients adaptively learn from continuous data streams. A significant challenge in CFL is mitigating catastrophic forgetting, where models lose previously acquired knowledge when learning new information. Existing approaches often face difficulties due to the constraints of device storage capacities and the heterogeneous nature of data distributions among clients. While some CFL algorithms have addressed these challenges, they frequently rely on unrealistic assumptions about the availability of task boundaries (i.e., knowing when new tasks begin). To address these limitations, we introduce Fed-A-GEM, a federated adaptation of the A-GEM method, which employs a buffer-based gradient projection approach. Fed-A-GEM alleviates catastrophic forgetting by leveraging local buffer samples and aggregated buffer gradients, thus preserving knowledge across multiple clients. Our method is combined with existing CFL techniques, enhancing their performance in the CFL context. Our experiments on standard benchmarks show consistent performance improvements across diverse scenarios. For example, in a task-incremental learning scenario using the CIFAR-100 dataset, our method can increase the accuracy by up to 27%. Our code is available at https://github.com/shenghongdai/Fed-A-GEM.

EUMAS Conference 2025 Conference Paper

Scalable Submodular Policy Optimization via Pruned Submodularity Graph

• Aditi Anand
• Suman Banerjee
• Dildar Ali

TMLR Journal 2025 Journal Article

Zoomer: Adaptive Image Focus Optimization for Black-box MLLM

• Jiaxu Qian
• Chendong Wang
• Yifan Yang
• Chaoyun Zhang
• Huiqiang Jiang
• Xufang Luo
• Yu Kang
• Qingwei Lin

Multimodal large language models (MLLMs) such as GPT-4o, Gemini Pro, and Claude 3.5 have enabled unified reasoning over text and visual inputs, yet they often hallucinate in real-world scenarios—especially when small objects or fine spatial context are involved. We pinpoint two core causes of this failure: the absence of region-adaptive attention and inflexible token budgets that force uniform downsampling, leading to critical information loss. To overcome these limitations, we introduce Zoomer a visual prompting framework that delivers token-efficient, detail-preserving image representations for black-box MLLMs. Zoomer integrates (1) a prompt-aware emphasis module to highlight semantically relevant regions, (2) a spatial-preserving orchestration schema to maintain object relationships, and (3) a budget-aware strategy to optimally allocate tokens between global context and local details. Extensive experiments on nine benchmarks and three commercial MLLMs demonstrate that Zoomer boosts accuracy by up to 27% while cutting image token usage by up to 67\%. Our approach establishes a principled methodology for robust, resource-aware multimodal understanding in settings where model internals are inaccessible.

AAAI Conference 2023 Short Paper

Efficient Algorithms for Regret Minimization in Billboard Advertisement (Student Abstract)

• Dildar Ali
• Ankit Kumar Bhagat
• Suman Banerjee
• Yamuna Prasad

Now-a-days, billboard advertisement has emerged as an effective outdoor advertisement technique. In this case, a commercial house approaches an influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider can satisfy this then they will receive the full payment else a partial payment. If the influence provider provides more or less than the demand then certainly this is a loss to them. This is formalized as ‘Regret’ and the goal of the influence provider will be to minimize the ‘Regret’. In this paper, we propose simple and efficient solution methodologies to solve this problem. Efficiency and effectiveness have been demonstrated by experimentation.

AAMAS Conference 2023 Conference Paper

Fairness Driven Efficient Algorithms for Sequenced Group Trip Planning Query Problem

• Napendra Solanki
• Shweta Jain
• Suman Banerjee
• Yayathi Pavan Kumar S

The Group Trip Planning Query Problem (GTP) is a well-researched spatial database problem. Given a city road network with Pointof-Interests (PoIs) representing vertices divided into different categories, GTP aims to suggest one PoI from each category to minimize the group’s total distance traveled. This paper focuses on sequenced GTP with pre-determined category visit order, studied under the constraints of fairness, and referred to as sequenced Fair Group Trip Planning Query Problem (Fair-GTP). While GTP aims to minimize the group’s total travel time, Fair-GTP seeks to minimize the maximum time difference between any two agents in the group. Although solving group trip planning queries is NP-hard, we present polynomial time algorithms for finding optimal paths for both sequenced GTP and Fair-GTP. Our second significant result provides a bound on the price of fairness (PoF) representing the ratio of optimal path cost in sequenced Fair-GTP to optimal path cost in sequenced GTP. We show that while the PoF can go arbitrarily bad for general sequenced Fair-GTP solutions, restricting to Paretooptimal solutions bounds the PoF by (2𝑏 − 1), where 𝑏 denotes the number of agents traveling in the group. We further show that this bound is tight. Finally, we present the performance analysis of our algorithms on real-world datasets, demonstrating that our solution approach recommends PoIs within reasonable computational time, and in practice, PoF is below 2.

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.