FPT Approximations for Connected Maximum Coverage
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912820320272384 |
|---|---|
| author | Inamdar, Tanmay Jana, Satyabrata Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket Zehavi, Meirav |
| author_facet | Inamdar, Tanmay Jana, Satyabrata Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket Zehavi, Meirav |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_08639 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | FPT Approximations for Connected Maximum Coverage Inamdar, Tanmay Jana, Satyabrata Kundu, Madhumita Lokshtanov, Daniel Saurabh, Saket Zehavi, Meirav Data Structures and Algorithms 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. |
| title | FPT Approximations for Connected Maximum Coverage |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.08639 |