# An Efficient Partitioning Oracle for Bounded-Treewidth Graphs

Authors: Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, Krzysztof Onak
Conference: The 15th International Workshop on Randomization and Computation (RANDOM 2011).


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/\eps))$ 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/\eps)$-time property testing algorithms for membership in these classes of graphs. Another application of the oracle is a $\poly(1/\eps)$-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive $\eps n$ in graphs with bounded treewidth. Finally, the oracle can be used to test in $\poly(1/\eps)$ time whether the input bounded-treewidth graph is $k$-colorable or perfect.

Full version: [PDF] [PS] [arXiv]
BibTeX: [DBLP]