On Efficient Distance Approximation for Graph Properties
share
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 P, 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 framework for using distance-approximation algorithms for "simple" properties to design distance-approximation. Applying this framework 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.
READ FULL TEXT