Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds

Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger

In the era of massive datasets, graph compression has become a vital tool for network analysis. Often, we are only interested in the distances between a specific subset of "terminal" nodes, while the rest of the graph serves as the underlying infrastructure. This paper, presented at ICALP 2016, investigates the fundamental limits of compressing graphs while approximately preserving these terminal distances. By establishing new lower and upper bounds, the authors provide a roadmap for the trade-offs between compressed graph size and distance accuracy.

The Compression Challenge: SPR vs. ATDP

The core of the research lies in two related problems: Steiner Point Removal (SPR) and Approximate Terminal Distance Preservation (ATDP). In SPR, the goal is to remove all non-terminal nodes (Steiner points) while keeping terminal distances within a multiplicative factor, known as distortion. ATDP is more flexible, allowing a small number of non-terminals to remain in the compressed graph to help minimize this distortion.

The authors focus on compression via minor operations—deleting or contracting edges and vertices. This approach is powerful because minors preserve structural properties; for instance, a minor of a planar graph remains planar. The challenge is to find a minor that is significantly smaller than the original graph but still provides a high-fidelity approximation of terminal distances.

Methodological Contributions

The paper's contributions are twofold: a novel framework for proving lower bounds and new algorithmic upper bounds for various graph classes.

Lower Bounds via Black-Box Reduction

The authors introduced a "black-box" reduction that links the difficulty of SPR to ATDP. They utilized Steiner Systems—combinatorial designs where subsets of elements overlap in specific ways—to embed multiple copies of a "hard" SPR instance into a larger graph. This construction demonstrates that even if one is allowed to retain a super-linear number of non-terminals, significant distortion remains unavoidable if the underlying SPR problem is difficult.

Illustration of a Steiner system (Fano plane) and its bipartite representation used in the lower bound construction.

Algorithmic Upper Bounds

To achieve efficient compression, the authors employed several advanced techniques:

  1. Spanners: Constructing subgraphs that maintain distance approximations with fewer edges.
  2. Shortest Path Separators: For planar graphs, the authors recursively partitioned the graph using shortest paths and utilized "portals" (a technique from Thorup) to approximate distances across these boundaries.
  3. Treewidth Decomposition: They adapted existing distance-preserving frameworks to work specifically with graphs of bounded treewidth.

Key Results and Insights

The research reveals that the compressibility of a graph is heavily dependent on its structural class. Planar graphs, for example, are highly compressible, achieving $(1 + \epsilon)$ distortion with only $O((k/\epsilon)^2)$ non-terminals. In contrast, general graphs require significantly more "scaffolding" to maintain accuracy.

Summary of upper and lower bounds for terminal distance preservation across various graph classes.

Key findings include:

  • General Graphs: To keep distortion below 2, at least $\Omega(k^2)$ non-terminals must be preserved. Conversely, $(2q - 1)$ distortion is achievable with $O(k^{2+2/q})$ non-terminals.
  • Planar Graphs: These can be compressed into a minor with $(1 + \epsilon)$ distortion using $O((k/\epsilon)^2)$ non-terminals, or distortion 3 with $O(k^2)$ non-terminals.
  • Bounded Treewidth: For graphs with treewidth $p$, $(2q - 1)$ distortion is possible with $O(p^{1+2/q}k)$ non-terminals.

Discussion and Future Directions

A major insight from this work is the "Linear Power" limit: if the best possible distortion for SPR grows with the number of terminals, then allowing a linear number of non-terminals ($O(k)$) will not reduce distortion to a constant.

Despite these advances, several gaps remain. For general graphs, there is a significant discrepancy at distortion 3, where the lower bound is $\Omega(k^{6/5})$ and the upper bound is $O(k^3)$. Additionally, the exact lower bound for SPR on general graphs remains unknown, currently ranging between 8 and $O(\log^5 k)$. Solving this would directly refine the ATDP bounds established here. Finally, developing deterministic minor-finding algorithms for excluded-minor graphs with $O(1)$ distortion remains a key open challenge.

Summary updated

BibTeX
@inproceedings{cheung2016graph,
  author = {Yun Kuen Cheung and Gramoz Goranci and Monika Henzinger},
  title = {{Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds}},
  booktitle = {ICALP},
  year = {2016},
  doi = {10.4230/lipics.icalp.2016.131},
}
Figure