  A primary challenge in metagenomics is reconstructing individual microbial
genomes from the mixture of short fragments created by sequencing. Recent work
leverages the sparsity of the assembly graph to find $r$-dominating sets which
enable rapid approximate queries through a dominator-centric graph partition.
In this paper, we consider two problems related to reducing uncertainty and
improving scalability in this setting.
  First, we observe that nodes with multiple closest dominators necessitate
arbitrary tie-breaking in the existing pipeline. As such, we propose finding
$\textit{sparse}$ dominating sets which minimize this effect via a new
$\textit{congestion}$ parameter. We prove minimizing congestion is NP-hard, and
give an $\mathcal{O}(\sqrt{\Delta^r})$ approximation algorithm, where $\Delta$
is the max degree.
  To improve scalability, the graph should be partitioned into uniformly sized
pieces, subject to placing vertices with a closest dominator. This leads to
$\textit{balanced neighborhood partitioning}$: given an $r$-dominating set,
find a partition into connected subgraphs with optimal uniformity so that each
vertex is co-assigned with some closest dominator. Using variance of piece
sizes to measure uniformity, we show this problem is NP-hard iff $r$ is greater
than $1$. We design and analyze several algorithms, including a polynomial-time
approach which is exact when $r=1$ (and heuristic otherwise).
  We complement our theoretical results with computational experiments on a
corpus of real-world networks showing sparse dominating sets lead to more
balanced neighborhood partitionings. Further, on the metagenome
$\textsf{HuSB1}$, our approach maintains high query containment and similarity
while reducing piece size variance.

Data Structures and Algorithms