6 papers
From One Solution to Many: An Oracle-Based FPT Framework for Diverse Solutions under Generalized Diversity Measures
Pradeesha Ashok, Sobyasachi Chatterjee, Soumi Nandi +2
The problem of computing \emph{diverse} solutions has recently emerged as an important area of study, motivated by applications in fairness, robustness, and security. Instead of re…
Fixed Budget vs. Covering Target: The Partial Set Cover Boundary for Bounded VC-Dimension
Madhumita Kundu, Souvik Saha, Saket Saurabh +1
Maximum Coverage and Partial Set Cover are fundamental parameterized covering problems. The former fixes a budget and maximizes coverage; the latter meets a target with as few…
Covering Points with Rectangular Boundaries
Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi +2
Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{boundary covering} variant, where…
FPT Approximations for Connected Maximum Coverage
Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu +3
We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph and an auxiliary connectivity…
More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
Sushmita Gupta, Pallavi Jain, Souvik Saha +2
Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. We contribute to this area by designing parameterized approximation algorit…
A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
Satyabrata Jana, Lawqueen Kanesh, Madhumita Kundu +2
In the Subset Feedback Arc Set in Tournaments, Subset-FAST problem we are given as input a tournament with a vertex set and an arc set , along with a terminal set…