Jump to content

Baker's technique: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
References: authorlink Hans L. Bodlaender; remove whitespace
m Reverted edit by Albinjm (talk) to last version by OAbot
 
(43 intermediate revisions by 19 users not shown)
Line 1: Line 1:
In [[theoretical computer science]], '''Baker's technique''' is a method for designing [[polynomial-time approximation scheme]]s (PTASs) for problems on [[planar graph]]s. It is named after [[Brenda Baker]], who announced it in a 1983 conference and published it in the ''[[Journal of the ACM]]'' in 1994.
{{orphan|date=December 2011}}


'''Baker's technique''', created 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, and bounded genus 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.
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. 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.

The [[bidimensionality|bidimensionality theory]] of [[Erik Demaine]], Fedor Fomin, [[Mohammad Hajiaghayi|Hajiaghayi]], and Dimitrios Thilikos and its offshoot ''simplifying decompositions'' ({{harvtxt|Demaine|Hajiaghayi|Kawarabayashi|2005}},{{harvtxt|Demaine|Hajiaghayi|Kawarabayashi|2011}}) 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]], 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.


==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 (graph theory)|independent set]] problem.


===Algorithm===
===Algorithm===
INDEPENDENT-SET(<math>G</math>,<math>w</math>,<math>\epsilon</math>)
INDEPENDENT-SET(<math>G</math>, <math>w</math>, <math>\epsilon</math>)
Choose an arbitrary vertex <math> r </math>
Choose an arbitrary vertex <math> r </math>
<math>k = 1/\epsilon</math>
<math>k = 1/\epsilon</math>
find the breadth-first search levels for <math> G </math> rooted at <math> r </math> <math>\pmod k</math>: <math>\{V_0,V_1, \ldots, V_{k-1} \}</math>
find the breadth-first search levels for <math> G </math> rooted at <math> r </math> <math>\pmod k</math>: <math>\{V_0,V_1, \ldots, V_{k-1} \}</math>
for <math>\ell = 0, \ldots, k-1</math>
find the components <math>G^\ell_1, G^\ell_2, \ldots,</math> of <math>G</math> after deleting <math>V_\ell</math>
'''for''' <math>\ell = 0, \ldots, k-1</math>
find the components <math>G^\ell_1, G^\ell_2, \ldots,</math> of <math>G</math> after deleting <math>V_\ell</math>
for <math>i = 1,2, \ldots </math>
compute <math>S_i^\ell</math>, the maximum-weight independent set of <math>G_i^\ell</math>
'''for''' <math>i = 1,2, \ldots </math>
compute <math>S_i^\ell</math>, the maximum-weight independent set of <math>G_i^\ell</math>
<math>S^\ell = \cup_i S_i^\ell</math>
let <math>S^{\ell^*}</math> be the solution of maximum weight among <math>\{S^0,S^1, \ldots, S^{k-1} \}</math>
<math>S^\ell = \cup_i S_i^\ell</math>
let <math>S^{\ell^*}</math> be the solution of maximum weight among <math>\{S^0,S^1, \ldots, S^{k-1} \}</math>
return <math>S^{\ell^*}</math>
'''return''' <math>S^{\ell^*}</math>


Notice that the above algorithm is feasible because each <math>S^\ell </math> is the union of disjoint independent sets.
Notice that the above algorithm is feasible because each <math>S^\ell </math> is the union of disjoint independent sets.


===Dynamic programming===
===Dynamic programming===
[[Dynamic programming]] is used when we compute the maximum-weight independent set for each <math>G_i^\ell</math>. This dynamic program works because each <math>G_i^\ell</math> is a <math>k</math>-[[outerplanar graph]]. Many NP-complete problems can be solved with dynamic programming on <math>k</math>-outerplanar graphs.
[[Dynamic programming]] is used when we compute the maximum-weight independent set for each <math>G_i^\ell</math>. This dynamic program works because each <math>G_i^\ell</math> is a [[K-outerplanar graph|<math>k</math>-outerplanar graph]]. Many NP-complete problems can be solved with dynamic programming on <math>k</math>-outerplanar graphs. Baker's technique can be interpreted as covering the given planar graphs with subgraphs of this type, finding the solution to each subgraph using dynamic programming, and gluing the solutions together.


==References==
==References==
{{refbegin|colwidth=30em}}
{{refbegin|colwidth=30em}}
* {{citation
*{{citation
| last = Baker| first = B.
| last = Baker | first = Brenda S. | author-link = Brenda Baker
| contribution = Approximation algorithms for NP-complete problems on planar graphs (preliminary version)
| journal = JACM
| doi = 10.1109/SFCS.1983.7
| pages = 265–273
| publisher = IEEE Computer Society
| title = 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7–9 November 1983
| year = 1983}}
*{{citation
| last = Baker | first = Brenda S. | author-link = Brenda Baker
| doi = 10.1145/174644.174650| s2cid = 9706753 | doi-access = free
| issue = 1
| journal = [[Journal of the ACM]]
| mr = 1369197
| pages = 153–180
| title = Approximation algorithms for NP-complete problems on planar graphs
| title = Approximation algorithms for NP-complete problems on planar graphs
| volume = 41
| volume = 41
| issue = 1
| year = 1994}}
| year = 1994}}.
* {{citation
* {{citation
| last = Bodlaender| first = H. | authorlink = Hans L. Bodlaender
| last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
| editor1-last = Lepistö | editor1-first = Timo
| journal = ICALP
| editor2-last = Salomaa | editor2-first = Arto
| title = Dynamic programming on graphs with bounded treewidth
| contribution = Dynamic programming on graphs with bounded treewidth
| year = 1988}}.
| doi = 10.1007/3-540-19488-6_110
* {{citation
| hdl = 1874/16258 | isbn = 978-3-540-19488-0 | hdl-access = free
| last1 = Demaine|first1 = E.|authorlink= Erik Demaine|last2 = Hajiaghayi|first2 = M.|last3 = Kawarabayashi|first3 = K.
| journal = FOCS
| pages = 105–118
| publisher = Springer
| title = Algorithmic graph minor theory: Decomposition, approximation, and coloring
| series = [[Lecture Notes in Computer Science]]
| volume = 46
| title = Automata, Languages and Programming, 15th International Colloquium, ICALP '88, Tampere, Finland, July 11–15, 1988, Proceedings
| year = 2005}}.
| volume = 317
| year = 1988}}
*{{citation
| last1 = Demaine | first1 = Erik D.
| last2 = Hajiaghayi | first2 = Mohammad Taghi
| last3 = Kawarabayashi | first3 = Ken-ichi
| contribution = Algorithmic graph minor theory: Decomposition, approximation, and coloring
| doi = 10.1109/SFCS.2005.14
|isbn = 0-7695-2468-0|s2cid = 13238254| url = http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf
| pages = 637–646
| publisher = IEEE Computer Society
| title = 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, Proceedings
| year = 2005}}
*{{citation
| last1 = Demaine | first1 = Erik D.
| last2 = Hajiaghayi | first2 = MohammadTaghi
| last3 = Kawarabayashi | first3 = Ken-ichi
| editor1-last = Fortnow | editor1-first = Lance
| editor2-last = Vadhan | editor2-first = Salil P.
| contribution = Contraction decomposition in J-minor-free graphs and algorithmic applications
| doi = 10.1145/1993636.1993696
| pages = 441–450
| publisher = ACM
| title = Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011
| year = 2011
| hdl = 1721.1/73855|isbn = 9781450306911|s2cid = 16516718| hdl-access = free}}
* {{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.
Line 49: Line 93:
| title = Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.
| title = Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.
| volume = 69
| volume = 69
| year = 2004}}.
| year = 2004
|issue = 2|pages = 166–195| doi = 10.1016/j.jcss.2003.12.001|doi-access = free}}.
* {{citation
* {{citation
| last = Eppstein| first = D.
| last = Eppstein| first = D.
Line 56: Line 101:
| title = Diameter and treewidth in minor-closed graph families.
| title = Diameter and treewidth in minor-closed graph families.
| volume = 27
| volume = 27
| doi=10.1007/s004530010020
| year = 2000}}.
| arxiv = math/9907126v1
* {{citation
| last = Eppstein| first = D.
| year = 2000| issue = 3
| pages = 275–291
| authorlink=David Eppstein
| journal = SODA
| s2cid = 3172160
}}.
| title = Subgraph isomorphism in planar graphs and related problems.
*{{citation
| volume = 6
| last = Eppstein | first = David | author-link = David Eppstein
| year = 1995}}.
| doi = 10.7155/jgaa.00014
| issue = 3
| journal = Journal of Graph Algorithms and Applications
| mr = 1750082
| pages = 1–27
| title = Subgraph isomorphism in planar graphs and related problems
| volume = 3
| year = 1999| s2cid = 2303110 | doi-access = free
}}
*{{citation
| last1 = Grigoriev | first1 = Alexander
| last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender
| doi = 10.1007/s00453-007-0010-x
| issue = 1
| journal = Algorithmica
| mr = 2344391
| pages = 1–11
| title = Algorithms for graphs embeddable with few crossings per edge
| volume = 49
| year = 2007| hdl = 1874/17980
| s2cid = 8174422
| url = https://cris.maastrichtuniversity.nl/en/publications/5984fed8-f0b5-4b0d-91fe-2ca15d158421
| hdl-access = free
}}.
{{refend}}


<!--- Categories --->
<!--- Categories --->




[[Category:1983 in computing]]

[[Category:Planar graphs]]

[[Category:Approximation algorithms]]

[[Category:Articles created via the Article Wizard]]
[[Category:Graph theory]]

Latest revision as of 13:53, 8 October 2024

In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994.

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. 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.

The bidimensionality theory of Erik Demaine, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot simplifying decompositions (Demaine, Hajiaghayi & Kawarabayashi (2005),Demaine, Hajiaghayi & Kawarabayashi (2011)) 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, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the 1-planar graphs.

Example of technique

[edit]

The example that we will use to demonstrate Baker's technique is the maximum weight independent set problem.

Algorithm

[edit]
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

[edit]

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. Baker's technique can be interpreted as covering the given planar graphs with subgraphs of this type, finding the solution to each subgraph using dynamic programming, and gluing the solutions together.

References

[edit]
  • Baker, Brenda S. (1983), "Approximation algorithms for NP-complete problems on planar graphs (preliminary version)", 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7–9 November 1983, IEEE Computer Society, pp. 265–273, doi:10.1109/SFCS.1983.7
  • Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, MR 1369197, S2CID 9706753
  • Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", in Lepistö, Timo; Salomaa, Arto (eds.), Automata, Languages and Programming, 15th International Colloquium, ICALP '88, Tampere, Finland, July 11–15, 1988, Proceedings, Lecture Notes in Computer Science, vol. 317, Springer, pp. 105–118, doi:10.1007/3-540-19488-6_110, hdl:1874/16258, ISBN 978-3-540-19488-0
  • Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: Decomposition, approximation, and coloring", 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, Proceedings (PDF), IEEE Computer Society, pp. 637–646, doi:10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, S2CID 13238254
  • Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi (2011), "Contraction decomposition in J-minor-free graphs and algorithmic applications", in Fortnow, Lance; Vadhan, Salil P. (eds.), Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011, ACM, pp. 441–450, doi:10.1145/1993636.1993696, hdl:1721.1/73855, ISBN 9781450306911, S2CID 16516718
  • 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 (2): 166–195, doi:10.1016/j.jcss.2003.12.001.
  • Eppstein, D. (2000), "Diameter and treewidth in minor-closed graph families.", Algorithmica, 27 (3): 275–291, arXiv:math/9907126v1, doi:10.1007/s004530010020, S2CID 3172160.
  • Eppstein, David (1999), "Subgraph isomorphism in planar graphs and related problems", Journal of Graph Algorithms and Applications, 3 (3): 1–27, doi:10.7155/jgaa.00014, MR 1750082, S2CID 2303110
  • 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, hdl:1874/17980, MR 2344391, S2CID 8174422.