On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs
AuthorsHendrik Fichtenberger,Pan Peng,Christian Sohler
- Part of: Volume:Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Part of: Series:Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference:International Conference on Randomization and Computation (RANDOM)
Part of: Conference:International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license - Publication Date: 2015-08-13
File
PDF
LIPIcs.APPROX-RANDOM.2015.786.pdf
- Filesize: 0.51 MB
- 14 pages
Document Identifiers
Subject Classification
Keywords
- local graph structure
- k-disc frequency vector
- graph property testing
Metrics
- Access Statistics
- Total Accesses (updated on a weekly basis)0PDF Downloads0Metadata Views
Abstract
Let G=(V,E) be an undirected graph with maximum degree d. The k-disc of a vertex v is defined as the rooted subgraph that is induced by all vertices whose distance to v is at most k. The k-disc frequency vector of G, freq(G), is a vector indexed by all isomorphism types of k-discs. For each such isomorphism type Gamma, the k-disc frequency vector counts the fraction of vertices that have k-disc isomorphic to Gamma. Thus, the frequency vector freq(G) of G captures the local structure of G. A natural question is whether one can construct a much smaller graph H such that H has a similar local structure. N. Alon proved that for any epsilon>0 there always exists a graph H whose size is independent of |V| and whose frequency vector satisfies ||freq(G) - freq(G)||_1 <= epsilon. However, his proof is only existential and neither gives an explicit bound on the size of H nor an efficient algorithm. He gave the open problem to find such explicit bounds. In this paper, we solve this problem for the special case of high girth graphs. We show how to efficiently compute a graph H with the above properties when G has girth at least 2k+2 and we give explicit bounds on the size of H.
Cite AsGet BibTex
Hendrik Fichtenberger, Pan Peng, and Christian Sohler. On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 786-799, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.786
Author Details
References
- D. Aldous and R. Lyons. Processes on Unimodular Random Networks. Electronic Journal of Probability, 12(54):1454-1508, 2007.
- A. Benczúr and D. Karger. Approximating s-t Minimum Cuts In Õ(n²) Time. In Proceedings of the 28th annual ACM Symposium on Theory of Computing, pages 47-55. ACM, 1996.
- I. Benjamini, O. Schramm, and A. Shapira. Every Minor-Closed Property of Sparse Graphs Is Testable. Advances in Mathematics, 223(6):2200-2218, 2010.
- P. Chew. There Are Planar Graphs Almost as Good as the Complete Graph. Journal of Computer and System Sciences, 39(2):205-219, 1989.
- G. Elek. On the Limit of Large Girth Graph Sequences. Combinatorica, 30(5):553-563, 2010.
- J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. American Mathematical Society, 2008.
- O. Goldreich and D. Ron. Property Testing in Bounded Degree Graphs. Algorithmica, 32:302-343, 2002.
- A. Hassidim, J. Kelner, H. Nguyen, and K. Onak. Local Graph Partitions for Approximation and Testing. In Proceedings of the 50th annual IEEE Symposium on Foundations of Computer Science, pages 22-31. IEEE, 2009.
- P. Indyk, A. McGregor, I. Newman, and K. Onak. Bertinoro workshop on sublinear algorithms 2011.http://sublinear.info/42. In Open Problems in Data Streams, Property Testing, and Related Topics, 2011.
- L. Lovász. Very Large Graphs. arXiv preprint arXiv:0902.0132, 2009.
- L. Lovász. Large Networks and Graph Limits. American Mathematical Society, 2012.
- B. McKay, N. Wormald, and B. Wysocka. Short Cycles in Random Regular Graphs. Electronic Journal of Combinatorics, 11(1):66, 2004.
- I. Newman and C. Sohler. Every Property of Hyperfinite Graphs Is Testable. SIAM Journal on Computing, 42(3):1095-1112, 2013.
- D. Spielman and S. Teng. Spectral Sparsification of Graphs. SIAM Journal on Computing, 40(4):981-1025, 2011.
- E. Szemerédi. Regular Partitions of Graphs. Technical report, DTIC Document, 1975.