3 papers
cs.DS2026
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…
cs.DS2026
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…
cs.DS2026
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 \),…