Access Restriction

Author Marko, Sharon ♦ Ron, Dana
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Recent Result ♦ Graph Property ♦ General Sparse Graph ♦ Subgraph-freeness Algorithm ♦ Distance-approximation Algorithm ♦ Bounded Degree ♦ Degree Bound ♦ Eulerian Graph ♦ Constant Size Subgraphs ♦ Dense-graphs Model ♦ Upper Bound ♦ Query Complexity ♦ Minimum Vertex Cover ♦ Edge Modification ♦ Distance Approximation ♦ Predetermined Graph Property ♦ Sublinear Algorithm ♦ Sublinear Time ♦ K-edge Connectivity
Description 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 = dn. 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 et. al. (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, 2002). 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).
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2006-01-01
Publisher Institution In Proceedings of the Tenth International Workshop on Randomization and Computation (RANDOM