Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909999185264640 |
|---|---|
| author | Fischer, Nick Künnemann, Marvin Redzic, Mirza |
| author_facet | Fischer, Nick Künnemann, Marvin Redzic, Mirza |
| contents | We revisit the classic Maximum $k$-Coverage problem: Determine the largest number $t$ of elements that can be covered by choosing $k$ sets from a given family $\mathcal{F} = \{S_1,\dots, S_n\}$ of a size-$u$ universe. A notable special case is Partial $k$-Dominating Set, where one chooses $k$ vertices in a graph to maximize the number of dominated vertices.
Extensive research has established strong hardness results for various aspects of Maximum $k$-Coverage, such as tight inapproximability results, $W[2]$-hardness, and a conditionally tight worst-case running time of $n^{k\pm o(1)}$. In this paper we ask: (1) Can this time bound be improved for small $t$, at least for Partial $k$-Dominating Set, ideally to time~$t^{k\pm O(1)}$? (2) More ambitiously, can we even determine the best-possible running time of Maximum $k$-Coverage with respect to the perhaps most natural parameters: the universe size $u$, the maximum set size $s$, and the maximum frequency $f$?
We successfully resolve both questions. (1) We give an algorithm that solves Partial $k$-Dominating Set in time $O(nt + t^{\frac{2ω}{3} k+O(1)})$ if $ω\ge 2.25$ and time $O(nt+ t^{\frac{3}{2} k+O(1)})$ if $ω\le 2.25$, where $ω\le 2.372$ is the matrix multiplication exponent. From this we derive a time bound that is conditionally optimal, regardless of $ω$, based on the well-established $k$-clique and 3-uniform hyperclique hypotheses from fine-grained complexity. We also obtain matching upper and lower bounds for sparse graphs. To address (2) we design an algorithm for Maximum $k$-Coverage running in time
$$
\min \left\{ (f\cdot \min\{\sqrt[3]{u}, \sqrt{s}\})^k + \min\{n,f\cdot \min\{\sqrt{u}, s\}\}^{kω/3}, n^k\right\}
\cdot g(k)n^{\pm O(1)}, $$ and, surprisingly, further show that this complicated time bound is also conditionally optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16923 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts Fischer, Nick Künnemann, Marvin Redzic, Mirza Data Structures and Algorithms We revisit the classic Maximum $k$-Coverage problem: Determine the largest number $t$ of elements that can be covered by choosing $k$ sets from a given family $\mathcal{F} = \{S_1,\dots, S_n\}$ of a size-$u$ universe. A notable special case is Partial $k$-Dominating Set, where one chooses $k$ vertices in a graph to maximize the number of dominated vertices. Extensive research has established strong hardness results for various aspects of Maximum $k$-Coverage, such as tight inapproximability results, $W[2]$-hardness, and a conditionally tight worst-case running time of $n^{k\pm o(1)}$. In this paper we ask: (1) Can this time bound be improved for small $t$, at least for Partial $k$-Dominating Set, ideally to time~$t^{k\pm O(1)}$? (2) More ambitiously, can we even determine the best-possible running time of Maximum $k$-Coverage with respect to the perhaps most natural parameters: the universe size $u$, the maximum set size $s$, and the maximum frequency $f$? We successfully resolve both questions. (1) We give an algorithm that solves Partial $k$-Dominating Set in time $O(nt + t^{\frac{2ω}{3} k+O(1)})$ if $ω\ge 2.25$ and time $O(nt+ t^{\frac{3}{2} k+O(1)})$ if $ω\le 2.25$, where $ω\le 2.372$ is the matrix multiplication exponent. From this we derive a time bound that is conditionally optimal, regardless of $ω$, based on the well-established $k$-clique and 3-uniform hyperclique hypotheses from fine-grained complexity. We also obtain matching upper and lower bounds for sparse graphs. To address (2) we design an algorithm for Maximum $k$-Coverage running in time $$ \min \left\{ (f\cdot \min\{\sqrt[3]{u}, \sqrt{s}\})^k + \min\{n,f\cdot \min\{\sqrt{u}, s\}\}^{kω/3}, n^k\right\} \cdot g(k)n^{\pm O(1)}, $$ and, surprisingly, further show that this complicated time bound is also conditionally optimal. |
| title | Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.16923 |