An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
复制标题
有界树宽图的高效分区预言机
DOI：
10.1007/978-3-642-22935-0_45
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Krzysztof Onak
中科院分区：
文献类型：
--
作者：
A. Edelman;Avinatan Hassidim;H. N. Nguyen;Krzysztof Onak
Hassidim等人引入了分区的甲壳。 （FOCS 2009）作为恒定时间算法的通用工具。对于任何E> 0，分区的Oracle提供查询访问输入有限度少量图的固定分区的查询访问，其中每个组件都具有大小poly（1/e），并且删除的边缘数量最多是EN ，其中n是图中的顶点数。
但是，Hassidim等人的甲骨文。对输入图进行指数级的查询，以回答有关分区的每个查询。在本文中，我们为具有恒定树宽的图形构建了一个有效的分区甲骨文。 Oracle仅对输入图的o（poly（1/e））查询以回答有关分区的每个查询。
有界树的示例类别类别包括用于固定K的K-OuterPlanar图，串联并行图，仙人掌图和伪井架。我们的甲骨文在这些图表中产生poly（1/e） - 时属性测试算法。甲骨文的另一个应用是poly（1/e） - 时间算法，该算法近似于最大匹配大小，最小顶点盖尺寸和最小主导设置大小，最高为具有界化树宽的添加剂EN。最后，甲骨文可用于在poly（1/e）的时间内测试，无论输入有界窗格图是k色还是完美。
Partitioning oracles were introduced by Hassidim et al. (FOCS 2009) as a generic tool for constant-time algorithms. For any e > 0, a partitioning oracle provides query access to a fixed partition of the input bounded-degree minor-free graph, in which every component has size poly(1/e), and the number of edges removed is at most en, where n is the number of vertices in the graph.
However, the oracle of Hassidim et al. makes an exponential number of queries to the input graph to answer every query about the partition. In this paper, we construct an efficient partitioning oracle for graphs with constant treewidth. The oracle makes only O(poly(1/e)) queries to the input graph to answer each query about the partition.
Examples of bounded-treewidth graph classes include k-outerplanar graphs for fixed k, series-parallel graphs, cactus graphs, and pseudoforests. Our oracle yields poly(1/e)-time property testing algorithms for membership in these classes of graphs. Another application of the oracle is a poly(1/e)-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive en in graphs with bounded treewidth. Finally, the oracle can be used to test in poly(1/e) time whether the input boundedtreewidth graph is k-colorable or perfect.