On Efficient Distance Approximation for Graph Properties

A distance-approximation algorithm for a graph property P in the adjacency-matrix model is given an approximation parameter ∊ ∊ (0, 1) and query access to the adjacency matrix of a graph G = ( V, E ). It is required to output an estimate of the distance between G and the closest graph G′ = ( V, E′ ) that satisfies, where the distance between graphs is the size of the symmetric difference between their edge sets, normalized by | V| 2. In this work we introduce property covers, as a basis for a methodology that uses distance-approximation algorithms for “simple” properties to design distance-approximation algorithms for more “complex” properties. Applying this methodology we present distance-approximation algorithms with poly(1/ ∊ ) query complexity for induced P 3 -freeness, induced P 4 -freeness, and Chordality. For induced C 4 -freeness our algorithm has query complexity exp(poly(1/ ∊ )). These complexities essentially match the corresponding known results for testing these properties and provide an exponential improvement on previously known results.

Authors

• Nimrod Fiat
• Dana Ron

Keywords

No keywords are indexed for this paper.