Approximating the distance to properties in bounded-degree and general sparse graphs
Approximating the distance to properties in bounded-degree and general sparse graphs
复制标题
近似有界度和一般稀疏图中属性的距离
DOI：
10.1145/1497290.1497298
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
S. Marko;D. Ron
我们解决了近似具有一些预定图属性P的有限度和一般稀疏图的距离的问题。也就是说，我们对估算边缘修改（添加或删除）的分数的sublrinear算法感兴趣，这些算法必须在图以使其获得。特别是，对于在N顶点上绑定D的图形，M = Dn。要执行这样的近似值，算法可能会要求其选择的任何顶点的程度，并可能要求任何顶点的邻居。
Parnas等人首先明确解决了估计拥有财产距离的问题。 [2006]。在图表的上下文中，Fischer和Newman [2007]在密集图模型中研究了这个问题。在此模型中，相对于N2进行边缘修改的分数，并且该算法可能要求其选择的任何一对顶点之间存在边缘。 Fischer和Newman表明，该模型中具有测试算法的每个图形属性，其查询复杂性与图的大小无关，也具有距离近似算法，具有与图形大小无关的查询复杂性。
在这项工作中，我们专注于有界度和一般的稀疏图，并为所有属性提供了具有有效测试算法的所有属性的算法，该算法由Goldreich and Ron [2002]提供。具体而言，这些属性是k边缘连接性，子图式FREENESS（用于恒定大小的子图），是欧拉图和循环freeNESS。我们的子图量算法的变体近似于sublinear时图的最小顶点盖的大小。帕纳斯和罗恩（Parnas and Ron）[2007]的最新结果改善了这种近似值。
We address the problem of approximating the distance of bounded-degree and general sparse graphs from having some predetermined graph property P. That is, we are interested in sublinear algorithms for estimating the fraction of edge modifications (additions or deletions) that must be performed on a graph so that it obtains P. This fraction is taken with respect to a given upper bound m on the number of edges. In particular, for graphs with degree bound d over n vertices, m = dn. To perform such an approximation the algorithm may ask for the degree of any vertex of its choice, and may ask for the neighbors of any vertex.
The problem of estimating the distance to having a property was first explicitly addressed by Parnas et al. [2006]. In the context of graphs this problem was studied by Fischer and Newman [2007] in the dense graphs model. In this model the fraction of edge modifications is taken with respect to n2, and the algorithm may ask for the existence of an edge between any pair of vertices of its choice. Fischer and Newman showed that every graph property that has a testing algorithm in this model, with query complexity independent of the size of the graph, also has a distance approximation algorithm with query complexity that is independent of the size of graph.
In this work we focus on bounded-degree and general sparse graphs, and give algorithms for all properties shown to have efficient testing algorithms by Goldreich and Ron [2002]. Specifically, these properties are k-edge connectivity, subgraph freeness (for constant-size subgraphs), being an Eulerian graph, and cycle freeness. A variant of our subgraph-freeness algorithm approximates the size of a minimum vertex cover of a graph in sublinear time. This approximation improves on a recent result of Parnas and Ron [2007].