Abstract
Vertex sparsification aims to reduce the number of vertices in a graph while preserving essential properties like multicommodity flows and min-cuts between a subset of terminal nodes. This paper establishes that for any unweighted tree, a vertex sparsifier containing only terminal nodes can achieve a quality factor of 2. We prove this bound is tight, even for simple star graphs, and extend our methodology to quasi-bipartite graphs. Additionally, we show that verifying the quality of a given sparsifier is co-NP-hard.
Introduction
In the field of graph compression, sparsification typically involves reducing the number of edges. Vertex sparsification is a more aggressive approach where the goal is to eliminate non-essential vertices. Consider a large network where only a small subset of nodes, the terminals $K$, are involved in communication. The objective is to construct a smaller graph $H$ containing $K$ such that the traffic capacity (flow) and bottlenecks (cuts) between terminals in $H$ closely approximate those in the original graph $G$.
While general graphs face significant lower bounds for vertex sparsification, this work focuses on trees. We investigate the optimal approximation factor achievable when the input graph is a tree and provide efficient algorithms for constructing such sparsifiers.
Methodology
The primary contribution of this work is an elegant randomized algorithm for tree sparsification.
Randomized Connected 0-extension
To eliminate non-terminal nodes, the algorithm "pushes" them toward their children. By rooting the tree and iteratively mapping non-terminal nodes farthest from the root to one of their children (chosen uniformly at random), the entire tree is eventually collapsed onto the terminal set.
Theoretical Framework
To analyze the quality of this mapping, we employ linear programming (LP) duality. While a deterministic mapping could lead to a poor quality factor of $k-1$, we demonstrate that the expected congestion of our randomized approach is at most 2. This probabilistic mapping ensures that the capacity of any cut in the sparsifier is at most twice the capacity of the corresponding cut in the original tree.
Furthermore, we provide a derandomization technique that allows the construction of these sparsifiers in $O(n + k^2\alpha(2k))$ time, utilizing a "Tree Product Query" data structure.
Key Results and Tightness
Our analysis reveals several fundamental properties of vertex sparsification:
- The Factor of 2 Limit: We prove that a factor of $2 - o(1)$ is an inherent mathematical limit for cut preservation in trees. Even for a star graph, where all terminals are leaves connected to a single central non-terminal, no sparsifier consisting only of terminals can achieve a better approximation.
- Flow vs. Cut Sparsifiers: We achieve a factor of 2 for flow sparsifiers. Since flow sparsifiers are strictly stronger than cut sparsifiers, this result automatically provides a 2-approximation for cuts.
- Quasi-Bipartite Graphs: We extend our results to quasi-bipartite graphs (where terminals form an independent set). By treating these graphs as collections of stars, we obtain a 2-quality flow sparsifier of size $|K|$. We also construct exact sparsifiers (quality 1) of size $O(2^k)$ for unweighted quasi-bipartite graphs.
Complexity and Verification
A surprising result of our study is the hardness of verification. While we provide efficient algorithms to construct a sparsifier, we prove that the decision problem—checking if a given graph $H$ is a valid sparsifier for a tree $T$ with a specific quality—is co-NP-hard for both cuts and single-source flows.
Conclusion and Future Work
This work establishes the optimal bound for vertex sparsification in unweighted trees and provides a robust framework for extending these results to more complex graph classes like quasi-bipartite graphs.
Future research directions include extending the 2-quality result to arbitrary weighted trees and closing the gap between the $O(2^{2^k})$ upper bound and $2^{\Omega(k)}$ lower bound for Mimicking Networks in general graphs.
Summary updated