Minimizing Congestion for Balanced Dominators

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.