7 papers
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…
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…
FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu +2
For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as paramete…
Fixed-Parameter Algorithms for Fair Hitting Set Problems
Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu +2
Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of…