FPT Approximations for Connected Maximum Coverage

Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

TL;DR

This paper introduces a general model for connectivity-constrained coverage problems and develops novel FPT approximation algorithms for it. These algorithms provide near-optimal solutions for a class of problems that are computationally hard, bridging the gap between theoretical hardness and practical approximation guarantees.

What Problem Does This Paper Address?

The paper tackles a class of problems that combine coverage requirements with connectivity constraints. Imagine you need to select a set of "red" resources (e.g., sensors, servers) to cover a certain number of "blue" elements (e.g., targets, users). The twist is that the selected red resources must also form a connected network according to a separate "connectivity graph." This problem, formalized as PARTIAL CONNECTED RED-BLUE DOMINATING SET (PARTIALCONRBDS), generalizes several known problems like Maximum Coverage, Connected Dominating Set, and Partial Vertex Cover. The challenge lies in finding solutions that are both close to optimal in terms of coverage and connectivity, while also being computationally feasible for large inputs, especially when parameterized by the desired solution size or coverage. The authors aim to understand the boundaries of what's computationally possible for these problems, particularly within the framework of Fixed-Parameter Tractability (FPT) approximations.

Methods

The paper introduces a unifying model that separates the connectivity constraints (via a graph $G_{conn}$) from the coverage aspect (via a bipartite graph $G_{cov}$). For algorithmic contributions, they develop FPT approximation schemes. A key technique is the use of "neighborhood sparsifiers" for a specific class of coverage graphs ($K_{a,d}$-free). These sparsifiers allow them to construct surrogate weight functions that help in finding approximate solutions. They also leverage techniques like conflict graphs and random separation (derandomized using lopsided-universal families) to manage the complexity. For exact solutions, they reduce the problem to RELAXED DIRECTED STEINER OUT-TREE.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unifying Model: The separation of connectivity ($G_{conn}$) and coverage ($G_{cov}$) into distinct graphs provides a flexible framework to model a wide range of problems.
  • Bridging Hardness and Approximability: The paper establishes tight theoretical bounds, showing where exact FPT algorithms are impossible (W[1]-hard, ETH-based inapproximability) and then provides FPT approximation schemes for specific, structurally restricted cases.
  • Neighborhood Sparsifiers: This is a novel technical contribution that allows for effective approximation by creating a sparser representation of the coverage graph while preserving essential neighborhood information for finding approximate solutions.
  • The "Sweet Spot": The research highlights that by imposing structural restrictions on the coverage graph (like being $K_{a,d}$-free), it becomes possible to achieve fine-grained FPT approximations, even when the connectivity graph is arbitrary.

Key Results

  • Hardness Results: PARTIALCONRBDS is shown to be W[1]-hard parameterized by $k$, even under strong restrictions on $G_{conn}$ and $G_{cov}$. Furthermore, assuming ETH, there are strong inapproximability results, meaning no polynomial-time algorithm can achieve good approximation ratios.
  • FPT Approximation Schemes (for $K_{a,d}$-free $G_{cov}$):
    • An Efficient Parameterized Approximation Scheme (EPAS) provides a connected solution of size at most $k$ that covers at least $(1-\varepsilon)t$ blue vertices, running in time $O^*(2^{O(k^2d/\varepsilon)})$.
  • A Parameterized Approximation Scheme (PAS) provides a connected solution of size at most $(1+\varepsilon)k$ that covers at least $t$ blue vertices, running in time $O^*(2^{O(kd(k^2+\log d))})$.
  • Exact Algorithm: An algorithm for PARTIALCONRBDS parameterized by $t$ runs in time $O^*( (2e)^t )$.

Limitations and Future Work

  • Parameter Dependence: The running times of the approximation schemes still have exponential dependence on parameters like $k$ and $d$. Improving these exponents is a direction for future work.
  • Tractable Classes: The current approximation schemes are for $K_{a,d}$-free coverage graphs. Exploring other tractable classes, such as those with bounded VC-dimension or geometric incidences, is a promising avenue.
  • Other Constraints: The paper suggests studying variants with different connectivity or structural constraints (e.g., independence, degree bounds, fault tolerance) and exploring lossy kernels.
  • Steiner Version: The paper introduces and provides an EPAS for a Steiner version of the problem, which could be useful as a subroutine.

Summary updated

Abstract

We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph $G$ and an auxiliary connectivity graph $G_{conn}$ on red vertices, and integers $k, t$, the task is to find a $k$-sized subset of red vertices that dominates at least $t$ blue vertices, and that induces a connected subgraph in $G_{conn}$. This formulation captures connected variants of Max Coverage, Partial Dominating Set, and Partial Vertex Cover studied in prior literature. After identifying (parameterized) inapproximability results inherited from known problems, we first show that the problem is fixed-parameter tractable by $t$. Furthermore, when the bipartite graph excludes $K_{d,d}$ as a subgraph, we design (resp. efficient) parameterized approximation schemes for approximating $t$ (resp. $k$). Notably, these FPT approximations do not impose any restrictions on $G_{conn}$. Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.
BibTeX
@inproceedings{inamdar2026fpt,
  author = {Tanmay Inamdar and Satyabrata Jana and Madhumita Kundu and Daniel Lokshtanov and Saket Saurabh and Meirav Zehavi},
  title = {{FPT Approximations for Connected Maximum Coverage}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.80},
}
Figure