FPT Approximations for Connected Maximum Coverage

We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set (PartialConRBDS). Given a bipartite graph G = (R∪ B, E) with red vertices R and blue vertices B, an auxiliary connectivity graph G₂₎₍₍ on R, and integers k, t, the task is to find a set S ⊆ R with |S| ≤ k such that G₂₎₍₍S is connected and S dominates at least t blue vertices. This formulation captures connected variants of Maximum Coverage Hochbaum-Rao, Inf. Proc. Lett. , 2020; D'Angelo-Delfaraz, AAMAS 2025, Partial Vertex Cover, and Partial Dominating Set Khuller et al. , SODA 2014; Lamprou et al. , TCS 2021 via standard encodings. Limits to parameterized tractability. PartialConRBDS is W1-hard parameterized by k even under strong restrictions: it remains hard when G₂₎₍₍ is a clique or a star and the incidence graph G is 3-degenerate, or when G is K₂, ₂-free. Inapproximability. For every ε > 0, there is no polynomial-time (1, 1-1/e+ε) -approximation unless 𝖯 = NP. Moreover, under ETH, no algorithm running in f (k) ⋅ n^o (k) time achieves an g (k) -approximation for k for any computable function g (⋅), or for any ε > 0, a (1-1/e+ε) -approximation for t. Graphical special cases. Partial Connected Dominating Set is W2-hard parameterized by k and inherits the same ETH-based f (k) ⋅ n^o (k) inapproximability bound as above; Partial Connected Vertex Cover is W1-hard parameterized by k. These hardness boundaries delineate a natural "sweet spot" for study: within appropriate structural restrictions on the incidence graph, one can still aim for fine-grained (FPT) approximations. Our algorithms. We solve PartialConRBDS exactly by reducing it to Relaxed Directed Steiner Out-Tree in time (2e) ᵗ ⋅ n^𝒪 (1). For biclique-free incidences (i. e. , when G excludes K₃, ₃ as an induced subgraph), we obtain two complementary parameterized schemes: - An Efficient Parameterized Approximation Scheme (EPAS) running in time 2^𝒪 (k² d/ε) ⋅ n^𝒪 (1) that either returns a connected solution of size at most k covering at least (1-ε) t blue vertices, or correctly reports that no connected size-k solution covers t; and - A Parameterized Approximation Scheme (PAS) running in time 2^𝒪 (kd (k²+log d) ) ⋅ n^𝒪 (1/ε) that either returns a connected solution of size at most (1+ε) k covering at least t blue vertices, or correctly reports that no connected size-k solution covers t. Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.