论文标题
关于图形属性的有效距离近似
On Efficient Distance Approximation for Graph Properties
论文作者
论文摘要
Graph属性$ \ MATHCAL {p} $的距离 - 附属算法给出了近似值参数$ε\ in（0,1）$，并查询访问图$ G =（v，e）$的邻接矩阵。需要在$ g $和最接近的图形$ g'=（v，e'）$之间输出\ emph {距离}的估计值，该$满足满足$ \ MATHCAL {p} $，其中图之间的距离是其边缘集合之间的对称差异的大小，并由其边缘集合（$ | v | v |^2 $都归一化）。在这项工作中，我们介绍了属性覆盖物，作为使用距离及距离的算法的框架，用于“简单”属性来设计距离及值。应用此框架，我们以$ poly（1/ε）$查询复杂度的诱因$ p_3 $ - feRESINES，诱导$ p_4 $ - $ - 弗雷斯和弦乐的距离。对于诱导的$ C_4 $ -FRESINES，我们的算法具有查询复杂性$ exp（poly（1/ε））$。这些复杂性基本上与测试这些特性的相应已知结果相匹配，并为先前已知的结果提供了指数改进。
A distance-approximation algorithm for a graph property $\mathcal{P}$ in the adjacency-matrix model is given an approximation parameter $ε\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'=(V,E')$ 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/ε)$ 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.
