11 citations · 23 across the 11 of their papers we have counts for
13 papers
Dominating Set with Quotas: Balancing Coverage and Constraints
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh +2
We study a natural generalization of the classical \textsc{Dominating Set} problem, called \textsc{Dominating Set with Quotas} (DSQ). In this problem, we are given a graph \( G \),…
Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
Sushmita Gupta, Sounak Modak, Saket Saurabh +1
A feedback vertex set (FVS) in a digraph is a subset of vertices whose removal makes the digraph acyclic. In other words, it hits all cycles in the digraph. Lokshtanov et al. [TALG…
How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach
Sushmita Gupta, Pallavi Jain, Saket Saurabh
In this paper we study a resource allocation problem that encodes correlation between items in terms of \conflict and maximizes the minimum utility of the agents under a conflict f…
More Effort Towards Multiagent Knapsack
Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman
In this paper, we study some multiagent variants of the knapsack problem. Fluschnik et al. [AAAI 2019] considered the model in which every agent assigns some utility to every item.…
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Sushmita Gupta, Pallavi Jain, Fahad Panolan +2
Partitioning a region into districts to favor a particular candidate or a party is commonly known as gerrymandering. In this paper, we investigate the gerrymandering problem in gra…
On the (Parameterized) Complexity of Almost Stable Marriage
Sushmita Gupta, Pallavi Jain, Sanjukta Roy +2
In the Stable Marriage problem. when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are inco…