Algorithms and Complexity Seminar
Monday, September 25, 2006, 4-5:15pm in 32-G575.
Approximating the distance to properties in sparse graphs
Dana Ron (Tel Aviv University)
We address the problem of approximating the distance of boundeddegree
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 n2, 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.
Host: Ronitt Rubinfeld
(The Algorithms
and Complexity Seminar series talks are usually held Mondays from
4-5:15pm in 32-G575.)