Lower bounds for graph embeddings and combinatorial preconditioners

ABSTRACT

Given a general graph G, a fundamental problem is to find a spanning tree H that best approximates G by some measure. Often this measure is some combination of the congestion and dilation of an embedding of G into H. One example is the routing time p(G, H) ≤ O (congestion + dilation), the number of steps necessary to route pairwise demands G on network links H in the store-and-forward packet routing model. Another is the condition number kf(G, H) ≤ O (congestion · dilation), the square root of which bounds the number of iterations necessary to solve a linear system with coefficient matrix G preconditioned by H using the classical conjugate gradient method. The algorithmic applications of being able to find (efficiently) a good tree approximation H for a graph G are numerous; but what if no good tree exists.In this paper, we seek to identify the class of graphs G which are intrinsically difficult to approximate by a particular measure. It is easily seen that with respect to routing time, G is hardest to approximate by a tree H precisely when it contains either long cycles (which yield high dilation)or large separators (which yield high congestion). We show that with respect to condition number, the existence of long cycles or large separators in G is sufficient but not necessary or it to be hardest to approximate, by demonstrating a nearly-linear lower bound or the case in which G is a square mesh. The proof uses concepts from circuit theory, linear algebra, and geometry, and it generalizes to the case in which H is a spanning subgraph of G of Euler characteristic k. The result has consequences or the design of preconditioners or symmetric M-matrices and perhaps also of communication networks.

REFERENCES

• 1: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 2: Marshall Bern , John R. Gilbert , Bruce Hendrickson , Nhat Nguyen , Sivan Toledo, Support-Graph Preconditioners, SIAM Journal on Matrix Analysis and Applications, v.27 n.4, p.930-951, 2006 [doi>10.1137/S0895479801384019]
• 3: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 4: E. Boman, D. Chen, B. Hendrickson, and S. Toledo. Maximum-Weight-Basis Preconditioners. To appear in Numerical Linear Algebra with Applications.
• 5: Erik G. Boman , Bruce Hendrickson, Support Theory for Preconditioning, SIAM Journal on Matrix Analysis and Applications, v.25 n.3, p.694-717, 2003 [doi>10.1137/S0895479801390637]
• 6: E. Boman and B. Hendrickson. On Spanning Tree Preconditioners. Manuscript, Sandia National Laboratory, 2001.
• 7: K. Gremban. Combinatorial Preconditioners or Sparse, Symmetric, Diagonally Dominant Linear Systems. Ph.D. Thesis, Carnegie Mellon University, 1996.
• 8: Keith D. Gremban , Gary L. Miller , Marco Zagha, Performance evaluation of a new parallel preconditioner, Proceedings of the 9th International Symposium on Parallel Processing, p.65-69, April 25-28, 1995
• 9: Anupam Gupta, Steiner points in tree metrics don't (really) help, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.220-227, January 07-09, 2001, Washington, D.C., United States
• 10: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 11: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 12: Anil Joshi, Topics in optimization and sparse linear systems, University of Illinois at Urbana-Champaign, Champaign, IL, 1997
• 13: T. Leighton, B. Maggs, and S. Rao. Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps. Combinatorica 14(2):167--186, 1994.
• 14: B. Maggs, G. Miller, O. Parekh, R. Ravi, and S.-L. Woo. M -Matrices Have Good Support Tree Preconditioners. Manuscript, 2002.
• 15: K. V. M. Naidu , H. Ramesh, Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic, Proceedings of the 22nd Conference Kanpur on Foundations of Software Technology and Theoretical Computer Science, p.301-310, December 12-14, 2002
• 16: Y. Rabinovich and R. Raz. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. Discrete and Computational Geometry 19:79--94, 1998.
• 17: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 18: J. Reif. Efficient Approximate Solution of Sparse Linear Systems. Computers and Mathematics with Applications 36(9):37--58, 1998.
• 19: Daniel A. Spielman , Shang-Hua Teng, Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31), Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.416, October 11-14, 2003
• 20: Daniel A. Spielman , Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007372]
• 21: P. Vaidya. Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners. Manuscript, 1990.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Conditioning; Linear systems (direct and iterative methods)

General Terms:
Algorithms, Theory

Keywords:
congestion, dilation, graph embeddings, preconditioning