Baker's technique: Difference between revisions

Content deleted Content added

Inline

Revision as of 05:46, 21 December 2011

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

Example of technique

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

Algorithm

INDEPENDENT-SET( $G$ , $w$ , $\epsilon$ )
Choose an arbitrary vertex  $r$ 
 $k=1/\epsilon$ 
find the breadth-first search levels for  $G$  rooted at  $r$   ${\pmod {k}}$ :  $\{V_{0},V_{1},\ldots ,V_{k-1}\}$ 
for  $\ell =0,\ldots ,k-1$ 
find the components  $G_{1}^{\ell },G_{2}^{\ell },\ldots ,$  of  $G$  after deleting  $V_{\ell }$ 
for  $i=1,2,\ldots$ 
compute  $S_{i}^{\ell }$ , the maximum-weight independent set of  $G_{i}^{\ell }$ 
 $S^{\ell }=\cup _{i}S_{i}^{\ell }$ 
let  $S^{\ell ^{*}}$  be the solution of maximum weight among  $\{S^{0},S^{1},\ldots ,S^{k-1}\}$ 
return  $S^{\ell ^{*}}$

Notice that the above algorithm is feasible because each $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 $G_{i}^{\ell }$ . This dynamic program works because each $G_{i}^{\ell }$ is a $k$ -outerplanar graph. Many NP-complete problems can be solved with dynamic programming on $k$ -outerplanar graphs.

References

Baker, B. (1994), "Approximation algorithms for NP-complete problems on planar graphs", JACM, 41 (1).

Bodlaender, H. (1988), "Dynamic programming on graphs with bounded treewidth", ICALP.

Demaine, E.; Hajiaghayi, M.; Kawarabayashi, K. (2005), "Algorithmic graph minor theory: Decomposition, approximation, and coloring", FOCS, 46.

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.

Eppstein, D. (2000), "Diameter and treewidth in minor-closed graph families.", Algorithmica, 27.

Eppstein, D. (1995), "Subgraph isomorphism in planar graphs and related problems.", SODA, 6.

@@ Line 1: / Line 1: @@
-'''Baker's technique''' was created in 1994 by Brenda Baker. This is a method for designing [[polynomial-time approximation scheme]]s, 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, 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.
+'''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.
 ==Example of technique==
@@ Line 12: / Line 12: @@
  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>
+ 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>
+ <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>
-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]] 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 <math>k</math>-[[outerplanar graph]]. Many NP-complete problems can be solved with dynamic programming on <math>k</math>-outerplanar graphs.
 ==References==