Local reconstructors and tolerant testers for connectivity and diameter

DOI10.1007/978-3-642-40328-6_29zbMATH Open1405.68239arXiv1208.2956OpenAlexW2126000837MaRDI QIDQ2851874FDOQ2851874

Authors: Andrea Campagna, Alan Guo, Ronitt Rubinfeld 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Abstract: A local property reconstructor for a graph property is an algorithm which, given oracle access to the adjacency list of a graph that is "close" to having the property, provides oracle access to the adjacency matrix of a "correction" of the graph, i.e. a graph which has the property and is close to the given graph. For this model, we achieve local property reconstructors for the properties of connectivity and $k$-connectivity in undirected graphs, and the property of strong connectivity in directed graphs. Along the way, we present a method of transforming a local reconstructor (which acts as a "adjacency matrix oracle" for the corrected graph) into an "adjacency list oracle". This allows us to recursively use our local reconstructor for $(k-1)$-connectivity to obtain a local reconstructor for $k$-connectivity. We also extend this notion of local property reconstruction to parametrized graph properties (for instance, having diameter at most $D$ for some parameter $D$) and require that the corrected graph has the property with parameter close to the original. We obtain a local reconstructor for the low diameter property, where if the original graph is close to having diameter $D$, then the corrected graph has diameter roughly 2D. We also exploit a connection between local property reconstruction and property testing, observed by Brakerski, to obtain new tolerant property testers for all of the aforementioned properties. Except for the one for connectivity, these are the first tolerant property testers for these properties.

Full work available at URL: https://arxiv.org/abs/1208.2956

Recommendations

• Property testing in bounded degree graphs
• Testing the \((s,t)\) connectivity of graphs and digraphs
• scientific article; zbMATH DE number 1418268
• scientific article; zbMATH DE number 1559556
• Testing the diameter of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distance in graphs (05C12) Connectivity (05C40)

Cited In (9)

• Title not available (Why is that?)
• Sample-based distance-approximation for subsequence-freeness
• Testing versus estimation of graph properties, revisited
• Sampling correctors
• Approximating the distance to monotonicity of Boolean functions
• Can we locally compute sparse connected subgraphs?
• Local algorithms for sparse spanning graphs
• Constructing near spanning trees with few local inspections
• Local computation algorithms for graphs of non-constant degrees

This page was built for publication: Local reconstructors and tolerant testers for connectivity and diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851874)