On Efficient Distance Approximation for Graph Properties

Abstract

A distance-approximation algorithm for a graph property $\mathcal{P}$ in the adjacency-matrix model is given an approximation parameter $\epsilon \in (0,1)$ and query access to the adjacency matrix of a graph $G=(V,E)$. It is required to output an estimate of the \emph{distance} between $G$ and the closest graph $G^{\prime }=(V,E^{\prime })$ that satisfies $\mathcal{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/\epsilon )$ 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/\epsilon ))$. These complexities essentially match the corresponding known results for testing these properties and provide an exponential improvement on previously known results.