On Efficient Distance Approximation for Graph Properties

01/06/2020
by   Nimrod Fiat, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset