Approximating the distance to properties in sparse graphs
Speaker: Dana Ron , Tel Aviv University
Date: September 25 2006
Time: 4:00PM to 5:30PM
Location: 32-G575 (Theory Lab)
Host: Ronitt Rubinfeld, CSAIL, MIT
Contact: Be Blackburn, 617 253-6098, imbe@mit.edu
Relevant URL: We address the problem of approximating the distance of bounded
degree and general sparse graphs from having some predetermined graph
property P. Namely, we are interested in sublinear algorithms for
estimating the fraction of edges that should be added to / removed from
a graph so that it obtains P. This fraction is taken with respect to a
given upper bound m on the number of edges. In particular, for graphs
with degree bound d over n vertices, m = d n. To perform such an
approximation the algorithm may ask for the degree of any vertex
of its choice, and may ask for the neighbors of any vertex.
The problem of estimating the distance to having a property was first
explicitly addressed by Parnas, Ron and Rubinfeld (ECCC 2004). In the
context of graphs this problem was studied by Fischer and Newman (FOCS 2005)
in the dense-graphs model. In this model the fraction of edge modifications
is taken with respect to n^2, and the algorithm may ask for the existence
of an edge between any pair of vertices of its choice. Fischer and Newman
showed that every graph property that has a testing algorithm in this
model with query complexity that is independent of the size of
the graph, also has a distance-approximation algorithm with query
complexity that is independent of the size of the graph.
In this work we focus on bounded-degree and general sparse graphs,
and give algorithms for all properties that were shown to have
efficient testing algorithms by Goldreich and Ron (Algorithmica).
Specifically, these properties are k-edge connectivity,
subgraph-freeness (for constant size subgraphs), being a Eulerian graph,
and cycle-freeness. A variant of our subgraph-freeness algorithm
approximates the size of a minimum vertex cover of a graph in sublinear time.
This approximation improves on a recent result of Parnas and Ron (ECCC 2005).
Joint work with Sharon Marko.
See other events that are part of Algorithms and Complexity Series 2006/2007
See other events happening in September 2006
