4 papers · 1 filter
Connected Dominating Set on Semi-Ladder-Free Graphs
Sobyasachi Chatterjee, Sushmita Gupta, Saket Saurabh +2
We study \textsc{Connected Dominating Set} on graphs whose closed-neighborhood set systems are -semi-ladder-free. This structural condition strictly generalizes the biclique-fre…
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…
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…