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 P3-freeness, induced P4-freeness, and Chordality. For induced C4-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.