An efficient partitioning oracle for bounded-treewidth graphs
From MaRDI portal
Abstract: Partitioning oracles were introduced by Hassidim et al. (FOCS 2009) as a generic tool for constant-time algorithms. For any epsilon > 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/epsilon), and the number of edges removed is at most epsilon*n, where n is the number of vertices in the graph. However, the oracle of Hassidimet 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/epsilon)) 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/epsilon)-time property testing algorithms for membership in these classes of graphs. Another application of the oracle is a poly(1/epsilon)-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive epsilon*n in graphs with bounded treewidth. Finally, the oracle can be used to test in poly(1/epsilon) time whether the input bounded-treewidth graph is k-colorable or perfect.
Recommendations
Cites work
- A Separator Theorem for Planar Graphs
- An improved constant-time approximation algorithm for maximum~matchings
- Applications of a Planar Separator Theorem
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Every property of hyperfinite graphs is testable
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. III. Planar tree-width
- scientific article; zbMATH DE number 5485551 (Why is no real title available?)
- scientific article; zbMATH DE number 4060712 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Local Graph Partitions for Approximation and Testing
- On digraph coloring problems and treewidth duality
- On the hardness of approximating minimum vertex cover
- On tree-partition-width
- Parameter testing in bounded degree graphs of subexponential growth
- Property testing in bounded degree graphs
- Recognizing Berge graphs
- Some results on tree decomposition of graphs
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- Testing outerplanarity of bounded degree graphs
Cited in
(7)- Vertex-coloring with star-defects
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Borel oracles. An analytical approach to constant-time algorithms
- Testing outerplanarity of bounded degree graphs
- The subgraph testing model
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
- Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
This page was built for publication: An efficient partitioning oracle for bounded-treewidth graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088124)
