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 𝑟 -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 sparse dominating sets which minimize this effect via a new congestion parameter. We prove minimizing congestion is NP-hard, and give an O ( √ Δ 𝑟 ) approximation algorithm, where Δ 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 balanced neighborhood partitioning: given an 𝑟 -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 𝑟 is greater than 1. We design and analyze several algorithms, including a polynomial-time approach which is exact when 𝑟 = 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 HuSB1, our approach maintains high query containment and similarity while reducing piece size variance.

• Theory of computation → Graph algorithms analysis.