Baker's technique: Difference between revisions
→References: authorlink Ken-ichi Kawarabayashi |
No edit summary |
||
Line 1: | Line 1: | ||
'''Baker's technique''', created in 1983 (conference presentation) and published in a journal in 1994 by Brenda Baker, is a method for designing [[polynomial-time approximation scheme]]s, PTASs, for problems on [[planar graph]]s. This technique has given PTASs for the following problems: [[subgraph isomorphism]], [[maximum independent set]], [[minimum vertex cover]], [[minimum dominating set]], minimum [[edge dominating set]], maximum triangle matching, and many others. Its generalizations have also led to many PTASs on graphs excluding a fixed minor, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the [[1-planar graph]]s. The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution. |
'''Baker's technique''', created in 1983 (conference presentation) and published in a journal in 1994 by Brenda Baker, is a method for designing [[polynomial-time approximation scheme]]s, PTASs, for problems on [[planar graph]]s. This technique has given PTASs for the following problems: [[subgraph isomorphism]], [[maximum independent set]], [[minimum vertex cover]], [[minimum dominating set]], minimum [[edge dominating set]], maximum triangle matching, and many others. Its generalizations have also led to many PTASs on graphs excluding a fixed minor, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the [[1-planar graph]]s. The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution. [[bidimensionality|Bidimensionality theory]] of [[Erik Demaine]], Fedor Fomin, [[Hajiaghayi]], and Dimitrios Thilikos and its offshoot ''simplifying decompistions'' generalizes and greatly expands the applicability of Baker's technique |
||
for a vast set of problems on [[planar graph]]s and more generally [[graph minor|graphs excluding a fixed minor]] and beyond. |
|||
==Example of technique== |
==Example of technique== |
||
The example that we will use to demonstrate Baker's technique is the maximum weight [[independent set]] problem. |
The example that we will use to demonstrate Baker's technique is the maximum weight [[independent set]] problem. |
||
Line 51: | Line 51: | ||
| year = 2005 |
| year = 2005 |
||
| doi = 10.1109/SFCS.2005.14}}. |
| doi = 10.1109/SFCS.2005.14}}. |
||
* {{citation |
|||
| last1 = Demaine|first1 = E.|authorlink= Erik Demaine|last2 = Hajiaghayi|first2 = M.|last3 = Kawarabayashi|first3 = K. | author3-link = Ken-ichi Kawarabayashi |
|||
| journal = STOC |
|||
| title = Contraction decomposition in H-minor-free graphs and algorithmic applications |
|||
| volume = 43 |
|||
| year = 2011 |
|||
| doi = 10.1145/1993636.1993696}}. |
|||
* {{citation |
* {{citation |
||
| last1 = Demaine|first1 = E.|authorlink= Erik Demaine|last2 = Hajiaghayi| first2 = M.|last3 = Nishimura|first3 = N.|last4 = Ragde|first4 = P.|last5 = Thilikos|first5 = D. |
| last1 = Demaine|first1 = E.|authorlink= Erik Demaine|last2 = Hajiaghayi| first2 = M.|last3 = Nishimura|first3 = N.|last4 = Ragde|first4 = P.|last5 = Thilikos|first5 = D. |
Revision as of 15:01, 21 November 2015
Baker's technique, created in 1983 (conference presentation) and published in a journal in 1994 by Brenda Baker, is a method for designing polynomial-time approximation schemes, PTASs, for problems on planar graphs. This technique has given PTASs for the following problems: subgraph isomorphism, maximum independent set, minimum vertex cover, minimum dominating set, minimum edge dominating set, maximum triangle matching, and many others. Its generalizations have also led to many PTASs on graphs excluding a fixed minor, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the 1-planar graphs. The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution. Bidimensionality theory of Erik Demaine, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot simplifying decompistions generalizes and greatly expands the applicability of Baker's technique for a vast set of problems on planar graphs and more generally graphs excluding a fixed minor and beyond.
Example of technique
The example that we will use to demonstrate Baker's technique is the maximum weight independent set problem.
Algorithm
INDEPENDENT-SET(,,) Choose an arbitrary vertex find the breadth-first search levels for rooted at : for find the components of after deleting for compute , the maximum-weight independent set of let be the solution of maximum weight among return
Notice that the above algorithm is feasible because each is the union of disjoint independent sets.
Dynamic programming
Dynamic programming is used when we compute the maximum-weight independent set for each . This dynamic program works because each is a -outerplanar graph. Many NP-complete problems can be solved with dynamic programming on -outerplanar graphs.
References
- Baker, B. (1994), "Approximation algorithms for NP-complete problems on planar graphs", JACM, 41 (1), doi:10.1145/174644.174650.
- Baker, B. (1983), "Approximation algorithms for NP-complete problems on planar graphs", FOCS, 24.
- Bodlaender, H. (1988), "Dynamic programming on graphs with bounded treewidth", ICALP, doi:10.1007/3-540-19488-6_110.
- Demaine, E.; Hajiaghayi, M.; Kawarabayashi, K. (2005), "Algorithmic graph minor theory: Decomposition, approximation, and coloring", FOCS, 46, doi:10.1109/SFCS.2005.14.
- Demaine, E.; Hajiaghayi, M.; Kawarabayashi, K. (2011), "Contraction decomposition in H-minor-free graphs and algorithmic applications", STOC, 43, doi:10.1145/1993636.1993696.
- Demaine, E.; Hajiaghayi, M.; Nishimura, N.; Ragde, P.; Thilikos, D. (2004), "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.", J. Comput. Syst. Sci., 69, doi:10.1016/j.jcss.2003.12.001.
- Eppstein, D. (2000), "Diameter and treewidth in minor-closed graph families.", Algorithmica, 27, arXiv:math/9907126v1, doi:10.1007/s004530010020.
- Eppstein, D. (1995), "Subgraph isomorphism in planar graphs and related problems.", SODA, 6.
- Grigoriev, Alexander; Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica, 49 (1): 1–11, doi:10.1007/s00453-007-0010-x, MR 2344391.