Baker's technique

<h2 id="example-of-technique">Example of technique</h2>
<p>The example that we will use to demonstrate Baker's technique is the maximum weight <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent set</a> problem.
</p>
<h3>Algorithm</h3>
INDEPENDENT-SET(
  
    
      
        G
      
    
    {\displaystyle G}
  
, 
  
    
      
        w
      
    
    {\displaystyle w}
  
, 
  
    
      
        ϵ
      
    
    {\displaystyle \epsilon }
  
)
    Choose an arbitrary vertex 
  
    
      
        r
      
    
    {\displaystyle r}

k
        =
        1
        
          /
        
        ϵ
      
    
    {\displaystyle k=1/\epsilon }

find the breadth-first search levels for 
  
    
      
        G
      
    
    {\displaystyle G}
  
 rooted at 
  
    
      
        r
      
    
    {\displaystyle r}
  
 
  
    
      
        
          
          (
          mod
          
          k
          )
        
      
    
    {\displaystyle {\pmod {k}}}
  
: 
  
    
      
        {
        
          V
          
            0
          
        
        ,
        
          V
          
            1
          
        
        ,
        …
        ,
        
          V
          
            k
            −
            1
          
        
        }
      
    
    {\displaystyle \{V_{0},V_{1},\ldots ,V_{k-1}\}}

for 
  
    
      
        ℓ
        =
        0
        ,
        …
        ,
        k
        −
        1
      
    
    {\displaystyle \ell =0,\ldots ,k-1}

find the components 
  
    
      
        
          G
          
            1
          
          
            ℓ
          
        
        ,
        
          G
          
            2
          
          
            ℓ
          
        
        ,
        …
        ,
      
    
    {\displaystyle G_{1}^{\ell },G_{2}^{\ell },\ldots ,}
  
 of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 after deleting 
  
    
      
        
          V
          
            ℓ
          
        
      
    
    {\displaystyle V_{\ell }}

for 
  
    
      
        i
        =
        1
        ,
        2
        ,
        …
      
    
    {\displaystyle i=1,2,\ldots }

compute 
  
    
      
        
          S
          
            i
          
          
            ℓ
          
        
      
    
    {\displaystyle S_{i}^{\ell }}
  
, the maximum-weight independent set of 
  
    
      
        
          G
          
            i
          
          
            ℓ
          
        
      
    
    {\displaystyle G_{i}^{\ell }}

S
          
            ℓ
          
        
        =
        
          ∪
          
            i
          
        
        
          S
          
            i
          
          
            ℓ
          
        
      
    
    {\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell }}

let 
  
    
      
        
          S
          
            
              ℓ
              
                ∗
              
            
          
        
      
    
    {\displaystyle S^{\ell ^{*}}}
  
 be the solution of maximum weight among 
  
    
      
        {
        
          S
          
            0
          
        
        ,
        
          S
          
            1
          
        
        ,
        …
        ,
        
          S
          
            k
            −
            1
          
        
        }
      
    
    {\displaystyle \{S^{0},S^{1},\ldots ,S^{k-1}\}}

return 
  
    
      
        
          S
          
            
              ℓ
              
                ∗
              
            
          
        
      
    
    {\displaystyle S^{\ell ^{*}}}

<p>Notice that the above algorithm is feasible because each 
  
    
      
        
          S
          
            ℓ
          
        
      
    
    {\displaystyle S^{\ell }}
  
 is the union of disjoint independent sets.
</p>
<h3>Dynamic programming</h3>
<p><a href="/facts/Dynamic_programming/CLcabtmk">Dynamic programming</a> is used when we compute the maximum-weight independent set for each 
  
    
      
        
          G
          
            i
          
          
            ℓ
          
        
      
    
    {\displaystyle G_{i}^{\ell }}
  
. This dynamic program works because each 
  
    
      
        
          G
          
            i
          
          
            ℓ
          
        
      
    
    {\displaystyle G_{i}^{\ell }}
  
 is a <a href="/facts/K-outerplanar_graph/vpsXfG9v">
  
    
      
        k
      
    
    {\displaystyle k}
  
-outerplanar graph</a>. Many NP-complete problems can be solved with dynamic programming on 
  
    
      
        k
      
    
    {\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.
</p>

<ul><li><a href="/facts/Brenda_Baker/XVzD2xfB">Baker, Brenda S.</a> (1983), "Approximation algorithms for NP-complete problems on planar graphs (preliminary version)", <i>24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7–9 November 1983</i>, IEEE Computer Society, pp. 265–273, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.1983.7">10.1109/SFCS.1983.7</a></li>
<li><a href="/facts/Brenda_Baker/XVzD2xfB">Baker, Brenda S.</a> (1994), "Approximation algorithms for NP-complete problems on planar graphs", <i><a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a></i>, 41 (1): 153–180, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F174644.174650">10.1145/174644.174650</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1369197">1369197</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:9706753">9706753</a></li>
<li><a href="/facts/Hans_L._Bodlaender/D7g6rsQ1">Bodlaender, Hans L.</a> (1988), "Dynamic programming on graphs with bounded treewidth", in Lepistö, Timo; Salomaa, Arto (eds.), <i>Automata, Languages and Programming, 15th International Colloquium, ICALP '88, Tampere, Finland, July 11–15, 1988, Proceedings</i>, <a href="/facts/Lecture_Notes_in_Computer_Science/1UeA77BC">Lecture Notes in Computer Science</a>, vol. 317, Springer, pp. 105–118, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-19488-6_110">10.1007/3-540-19488-6_110</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1874%2F16258">1874/16258</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-19488-0</li>
<li>Demaine, Erik D.; Hajiaghayi, Mohammad Taghi; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: Decomposition, approximation, and coloring", <a href="http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf"><i>46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23–25 October 2005, Pittsburgh, PA, USA, Proceedings</i></a> (PDF), IEEE Computer Society, pp. 637–646, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1109%2FSFCS.2005.14">10.1109/SFCS.2005.14</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-7695-2468-0, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:13238254">13238254</a></li>
<li>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.), <i>Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6–8 June 2011</i>, ACM, pp. 441–450, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F1993636.1993696">10.1145/1993636.1993696</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1721.1%2F73855">1721.1/73855</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450306911, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:16516718">16516718</a></li>
<li><a href="/facts/Erik_Demaine/qby54dWx">Demaine, E.</a>; Hajiaghayi, M.; Nishimura, N.; Ragde, P.; Thilikos, D. (2004), "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors.", <i>J. Comput. Syst. Sci.</i>, 69 (2): 166–195, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jcss.2003.12.001">10.1016/j.jcss.2003.12.001</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, D.</a> (2000), "Diameter and treewidth in minor-closed graph families.", <i>Algorithmica</i>, 27 (3): 275–291, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/math/9907126v1">math/9907126v1</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs004530010020">10.1007/s004530010020</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:3172160">3172160</a>.</li>
<li><a href="/facts/David_Eppstein/hIjTU6nC">Eppstein, David</a> (1999), "Subgraph isomorphism in planar graphs and related problems", <i>Journal of Graph Algorithms and Applications</i>, 3 (3): 1–27, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.7155%2Fjgaa.00014">10.7155/jgaa.00014</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1750082">1750082</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:2303110">2303110</a></li>
<li>Grigoriev, Alexander; <a href="/facts/Hans_L._Bodlaender/D7g6rsQ1">Bodlaender, Hans L.</a> (2007), <a href="https://cris.maastrichtuniversity.nl/en/publications/5984fed8-f0b5-4b0d-91fe-2ca15d158421">"Algorithms for graphs embeddable with few crossings per edge"</a>, <i>Algorithmica</i>, 49 (1): 1–11, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00453-007-0010-x">10.1007/s00453-007-0010-x</a>, <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/1874%2F17980">1874/17980</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2344391">2344391</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8174422">8174422</a>.</li></ul>

Baker's technique open-in-new

Baker's technique