Baker's technique

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

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

Algorithm

INDEPENDENT-SET(${\displaystyle G}$, ${\displaystyle w}$, ${\displaystyle \epsilon }$)
    Choose an arbitrary vertex ${\displaystyle r}$
    ${\displaystyle k=1/\epsilon }$
    find the breadth-first search levels for ${\displaystyle G}$ rooted at ${\displaystyle r}$ ${\displaystyle {\pmod {k}}}$: ${\displaystyle \{V_{0},V_{1},\ldots ,V_{k-1}\}}$

    for ${\displaystyle \ell =0,\ldots ,k-1}$
        find the components ${\displaystyle G_{1}^{\ell },G_{2}^{\ell },\ldots ,}$ of ${\displaystyle G}$ after deleting ${\displaystyle V_{\ell }}$

    for ${\displaystyle i=1,2,\ldots }$
       compute ${\displaystyle S_{i}^{\ell }}$, the maximum-weight independent set of ${\displaystyle G_{i}^{\ell }}$

    ${\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell }}$
    let ${\displaystyle S^{\ell ^{*}}}$ be the solution of maximum weight among ${\displaystyle \{S^{0},S^{1},\ldots ,S^{k-1}\}}$

    return ${\displaystyle S^{\ell ^{*}}}$

Notice that the above algorithm is feasible because each ${\displaystyle S^{\ell }}$ is the union of disjoint independent sets.

Dynamic programming

Dynamic programming is used when we compute the maximum-weight independent set for each ${\displaystyle G_{i}^{\ell }}$. This dynamic program works because each ${\displaystyle G_{i}^{\ell }}$ is a ${\displaystyle k}$-outerplanar graph. Many NP-complete problems can be solved with dynamic programming on ${\displaystyle k}$-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

• Baker, B. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
• 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, Lecture Notes in Computer Science, 317: 105–118, doi:10.1007/3-540-19488-6_110, ISBN 978-3-540-19488-0.
• Demaine, E.; Hajiaghayi, M.; Kawarabayashi, K. (2005), "Algorithmic graph minor theory: Decomposition, approximation, and coloring" (PDF), FOCS, 46: 637–646, doi:10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, S2CID 13238254.
• Demaine, E.; Hajiaghayi, M.; Kawarabayashi, K. (2011), "Contraction decomposition in H-minor-free graphs and algorithmic applications", STOC, 43: 441, 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, 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, hdl:1874/17980, MR 2344391, S2CID 8174422.