Local graph partitions for approximation and testing
We introduce a new tool for approximation and testing algorithms called partitioning oracles. We develop methods for constructing them for any class of bounded-degree graphs with an excluded minor, and in general, for any hyperfinite class of bounded-degree graphs. These oracles utilize only local c...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/59442 https://orcid.org/0000-0002-4257-4198 |
| _version_ | 1826207364359913472 |
|---|---|
| author | Hassidim, Avinatan Kelner, Jonathan Adam Nguyen, Huy N. Onak, Krzysztof |
| author2 | Massachusetts Institute of Technology. Department of Materials Science and Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Materials Science and Engineering Hassidim, Avinatan Kelner, Jonathan Adam Nguyen, Huy N. Onak, Krzysztof |
| author_sort | Hassidim, Avinatan |
| collection | MIT |
| description | We introduce a new tool for approximation and testing algorithms called partitioning oracles. We develop methods for constructing them for any class of bounded-degree graphs with an excluded minor, and in general, for any hyperfinite class of bounded-degree graphs. These oracles utilize only local computation to consistently answer queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges. We illustrate the power of this technique by using it to extend and simplify a number of previous approximation and testing results for sparse graphs, as well as to provide new results that were unachievable with existing techniques. For instance:1. We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor.2. We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model.3. We prove that it is possible to approximate the distance to almost any hereditary property in any bounded degree hereditary families of graphs. Hereditary properties of interest include bipartiteness, k-colorability, and perfectness. |
| first_indexed | 2024-09-23T13:48:27Z |
| format | Article |
| id | mit-1721.1/59442 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:48:27Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/594422022-09-28T16:19:53Z Local graph partitions for approximation and testing Hassidim, Avinatan Kelner, Jonathan Adam Nguyen, Huy N. Onak, Krzysztof Massachusetts Institute of Technology. Department of Materials Science and Engineering Kelner, Jonathan Adam Hassidim, Avinatan Kelner, Jonathan Adam Nguyen, Huy N. Onak, Krzysztof constant time algorithms approximation algorithms separator theorem We introduce a new tool for approximation and testing algorithms called partitioning oracles. We develop methods for constructing them for any class of bounded-degree graphs with an excluded minor, and in general, for any hyperfinite class of bounded-degree graphs. These oracles utilize only local computation to consistently answer queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges. We illustrate the power of this technique by using it to extend and simplify a number of previous approximation and testing results for sparse graphs, as well as to provide new results that were unachievable with existing techniques. For instance:1. We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor.2. We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model.3. We prove that it is possible to approximate the distance to almost any hereditary property in any bounded degree hereditary families of graphs. Hereditary properties of interest include bipartiteness, k-colorability, and perfectness. National Science Foundation (U.S.) (0732334) National Science Foundation (U.S.) (0728645) National Science Foundation (U.S.) (CCF-0843915) National Science Foundation (U.S.) (CCF-0832997) Symantec Research Labs Graduate Fellowship W. M. Keck Foundation Center for Extreme Quantum Information Theory Akamai Technologies, Inc. 2010-10-21T15:22:39Z 2010-10-21T15:22:39Z 2010-03 2009-10 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5116-6 0272-5428 INSPEC Accession Number: 11207160 http://hdl.handle.net/1721.1/59442 Hassidim, A. et al. “Local Graph Partitions for Approximation and Testing.” Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on. 2009. 22-31. ©2010 Institute of Electrical and Electronics Engineers. https://orcid.org/0000-0002-4257-4198 en_US http://dx.doi.org/10.1109/FOCS.2009.77 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. FOCS '09 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | constant time algorithms approximation algorithms separator theorem Hassidim, Avinatan Kelner, Jonathan Adam Nguyen, Huy N. Onak, Krzysztof Local graph partitions for approximation and testing |
| title | Local graph partitions for approximation and testing |
| title_full | Local graph partitions for approximation and testing |
| title_fullStr | Local graph partitions for approximation and testing |
| title_full_unstemmed | Local graph partitions for approximation and testing |
| title_short | Local graph partitions for approximation and testing |
| title_sort | local graph partitions for approximation and testing |
| topic | constant time algorithms approximation algorithms separator theorem |
| url | http://hdl.handle.net/1721.1/59442 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT hassidimavinatan localgraphpartitionsforapproximationandtesting AT kelnerjonathanadam localgraphpartitionsforapproximationandtesting AT nguyenhuyn localgraphpartitionsforapproximationandtesting AT onakkrzysztof localgraphpartitionsforapproximationandtesting |