Fichtenberger, Hendrik ;
Peng, Pan ;
Sohler, Christian
On ConstantSize Graphs That Preserve the Local Structure of HighGirth Graphs
Abstract
Let G=(V,E) be an undirected graph with maximum degree d. The kdisc 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 kdisc frequency vector of G, freq(G), is a vector indexed by all isomorphism types of kdiscs. For each such isomorphism type Gamma, the kdisc frequency vector counts the fraction of vertices that have kdisc 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.
BibTeX  Entry
@InProceedings{fichtenberger_et_al:LIPIcs:2015:5336,
author = {Hendrik Fichtenberger and Pan Peng and Christian Sohler},
title = {{On ConstantSize Graphs That Preserve the Local Structure of HighGirth Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {786799},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5336},
URN = {urn:nbn:de:0030drops53363},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.786},
annote = {Keywords: local graph structure, kdisc frequency vector, graph property testing}
}
13.08.2015
Keywords: 

local graph structure, kdisc frequency vector, graph property testing 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Issue date: 

2015 
Date of publication: 

13.08.2015 