A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
复制标题
排除次要图的拟多项式时间划分预言机
DOI：
10.1145/2629508
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
Reut Levi;D. Ron
受平面性及其相关性质测试问题的启发，我们研究了有效划分预言的设计问题。划分预言是这样一个过程，在给定对有界度图G=(V，E)的关联表表示和参数ε的访问时，当在顶点v∈V上查询时，返回v在所有图顶点的划分中所属的部分(顶点子集)。划分应该是这样的：所有部分都很小，每个部分都是连通的，如果图具有某些性质，则部分之间的边总数至多为ε|V|。在这项工作中，我们给出了1/ε中查询复杂度为拟多项式的含排除子式图的划分预言，改进了Hassidim等人的结果。(Focs2009)，他给出了一个查询复杂度为1/ε指数的划分预言。这一改进意味着在测试平面性和以排除子项为特征的其他属性的复杂性方面，以及在图具有排除子项的承诺下工作的次线性时间近似算法的相应改进。
Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient partition oracles. A partition oracle is a procedure that, given access to the incidence lists representation of a bounded-degree graph G= (V,E) and a parameter ε, when queried on a vertex v ∈ V, returns the part (subset of vertices) that v belongs to in a partition of all graph vertices. The partition should be such that all parts are small, each part is connected, and if the graph has certain properties, the total number of edges between parts is at most ε |V|. In this work, we give a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in 1/ε, improving on the result of Hassidim et al. (Proceedings of FOCS 2009), who gave a partition oracle with query complexity exponential in 1/ε. This improvement implies corresponding improvements in the complexity of testing planarity and other properties that are characterized by excluded minors as well as sublinear-time approximation algorithms that work under the promise that the graph has an excluded minor.