Prof. Meirav Zehavi

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 Gconn on R, and integers k, t, the task is to find a set S ⊆ R with |S| ≤ k such that Gconn[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.