Bakers Technique Designing Approximation Schemes For Planar Graphs

In 1994, Brenda Baker described a method for designing approximation algorithms for planar graphs [^B. Baker, Approximation algorithms for NP-complete problems on planar graphs, JACM Volume 41 Issue 1, Jan. 1994.^]. The technique results in an algorithm with approximation ratio {$1\pm\epsilon$} and running time {$2^{O(1/\epsilon)}n$}. Such a trade-off between running time and approximation ratio is called an approximation scheme; when the running time is polynomial for fixed {$\epsilon$}, it is a polynomial-time approximation scheme or PTAS.

The method applies to a host of problems. We describe the method using maximum-weight independent set as our example problem [^The technique can be viewed as an application of the layering technique as described in Section 2.2 in Approximation Algorithms by Vazirani.^].

Layering technique

The layering technique for designing an approximation algorithm for a given problem has two key parts:

break the input into layers such that the given problem can be solved optimally in each layer
taking the union of the solutions in each layer results in a feasible solution to the original input

When applied to planar graphs, we partition the vertices of the graph into layers. For maximum independent set, each layer needs to be independent to guarantee that the union of the layers' solutions are feasible for the original graph.

Attach:Baker.png Δ | The layers of a planar graph.
Consider an embedding of the planar graph {$G = (V,E)$}. We label each vertex according to their depth from the boundary of the graph: the vertices on the boundary of the graph are given label 0; the vertices with label {$i$} are on the boundary of the graph obtained by deleting the vertices with label {$0,1,\ldots,i-1$}. Let {$V_\ell$} be the set of vertices with label {$\ell \bmod k$} ({$k$} is a parameter that will be fixed later). Let {$G^\ell_1, G^\ell_2, \ldots,$} be the components of {$G$} that are obtained by deleting {$V_\ell$}. These components are the layers. By construction, {$G^\ell_j$} is a planar graph with {$k-1$} labels; we call such graphs {$(k-1)$}-outerplanar graphs, more on that below. Problems such as maximum-weight independent set can be solved optimally in {$2^{O(k)} n$} time in such graphs.

The algorithm

To motivate the algorithm, we start with some observations. Let {$S^*$} be the maximum-weight independent set of vertices in the graph {$G = (V,E)$}. {$\{V_0,V_1, \ldots, V_{k-1} \}$} is a partition of the vertices of the graph; it can be used to partition {$S^*$} as well, giving us {$\sum_{\ell = 0}^{k-1} w(S^* \cap V_\ell) = w(S^*)$}. It follows that {$\min_\ell w(S^* \cap V_\ell) \leq {1\over k} w(S^*)$}.

Let {$V_{\ell^*}$} be the set in the partition that witnesses this minimum contribution to the optimal solution. Let {$S_i^{\ell^*}$} be the maximum-weight independent set of {$G_i^{\ell^*}$}. Since independent sets are independent sets of subgraphs too, {$S^* \cap G_i^{\ell^*}$} is an independent set of {$G_i^{\ell^*}$} and so {$w(S_i^{\ell^*}) \geq w(S^* \cap G_i^{\ell^*})$}. So, if we take the union of the solutions for each layer {$\cup_i S_i^{\ell^*}$}, we get a solution whose weight is at least {$\sum_i w(S^* \cap G_i^{\ell^*}) = w(S^*) - w(S^* \cap V_{\ell^*})$}. By the choice of {$\ell^*$}, this is at least {$(1-{1\over k})w(S^*)$}. Using {$k = {1\over \epsilon}$}, the solution {$\cup_i S_i^{\ell^*}$} approximates {$S^*$} within {$1-\epsilon$} as desired. However, in order to find {$\cup_i S_i^{\ell^*}$} we needed to know {$\ell^*$}, which in turn required knowing {$S^*$}, the optimal solution to the problem we were trying to compute.

However, as {$\ell^*$} can only be one of {$k$} values we can simply try each value:

 INDEPENDENT-SET({$G$},{$w$},{$\epsilon$})
      {$k = 1/\epsilon$}
      find the levels of outerplanarity {$\pmod k$}: {$\{V_0,V_1, \ldots, V_{k-1} \}$}
      for {$\ell = 0, \ldots, k-1$}
           find the components {$G^\ell_1, G^\ell_2, \ldots,$} of {$G$} after deleting {$V_\ell$}
           for {$i = 1, \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^*}$}

If one can find the maximum-weight independent sets in each {$G_i^{\ell}$} in {$2^{O(k)} |G_i^{\ell}|$} time, then this algorithm runs in {$2^{O(k)}k n$} time.
It remains to show that we can compute the maximum-weight independent set in {$G_i^{\ell}$} in {$2^{O(k)} |G_i^{\ell}|$} time. By construction, we know {$G_i^{\ell}$} is a {$(k-1)$}-outerplanar graph. Usually one argues the solvability of such problems as maximum-weight independent set in {$(k-1)$}-outerplanar graphs by quoting two theorems:

Theorem: {$k$}-outerplanar graphs have treewidth {$3k-1$} and the corresponding tree decomposition can be found in linear time. [^H. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, Volume 209, Issues 1-2, 6 December 1998, Pages 1-45.^]

Theorem: Given a tree decomposition of a graph of treewidth {$tw$}, maximum-weight independent set can be solved optimally in {$2^{O(tw)} n$} time. [^For example, M. Bern, E. Lawler, A. Wong, Linear-time computation of optimal subgraphs of decomposable graphs, Journal of Algorithms 8 (2): 216�235, 1987.^]

Rather than prove these theorems at the expense of several pages here, we show how to solve maximum-weight independent set in a {$(k-1)$}-innerplanar graph. Innerplanar graphs are a special case of outerplanar graphs and the ingredients used below will (hopefully) impart the intuition and ingredients of the above two theorems.

Solving maximum-weight independent set in a {$k$}-innerplanar graph

400px|thumb|right|A 3-innerplanar graph (left) and 3-outerplanar graph (right). Vertices are coloured according to their label (red = 1, blue = 2, green = 3)? First, let's formally define inner- and outerplanarity. A planar graph that can be drawn so that all the vertices are on the boundary of the graph is an outerplanar graph (or 1-outerplanar graph). A single vertex is innerplanar (or 0-innerplanar). A {$k$}-innerplanar graph is a planar graph obtained from a {$(k-1)$}-innerplanar graph {$G$} by adding a simple cycle {$C$} and connecting vertices of {$C$} to vertices on the boundary of {$G$}. A planar graph is {$k$}-outerplanar if one deletes the vertices on the boundary of the graph and obtains a {$(k-1)$}-outerplanar graph. Note that a {$(k+1)$}-innerplanar graph is a {$k$}-outerplanar, but not vice versa.

Consider a {$k$}-innerplanar graph {$G$} with vertices labelled according to their level in the above definition, with the boundary vertices labelled {$k$}. We add edges of the form {$(i,i+1)$} to {$G$} while maintaing planarity (and so also maintain {$k$}-innerplanarity) so that each edge of label {$i > 1$} has a neighbour with label {$i-1$}. Call the resulting graph {$\bar G$}.

Claim: {$\bar G$} has a spanning tree {$T$} such that the longest simple path in {$T$} has at most {$2k+1$} nodes.

Proof: For each vertex {$x$} with labelled {$\ell(x) > 0$}, let {$n(x)$} be a node labelled {$\ell(x)-1$}. The set of edges {$T = \cup_{x:\ell(x) > 0} (x,n(x))$} forms a spanning tree. Node is at most {$\ell(x)$} edges away from the unique node of label 0 in this tree; the longest path in this tree has
{$2k+1$} nodes.

Without dwelling too much on the details of planar graphs, we use the following:

250px|thumb|left|A planar graph (black/grey) and its dual (red) with primal and dual spanning trees (dark)? Theorem: The set of non-tree edges forms a spanning tree of the dual graph of {$\bar G$} whose vertices are the faces of {$\bar G$} with vertex adjacencies inherited from face adjacencies.

We use this dual spanning tree to guide a dynamic program we use to solve maximum-weight independent set optimally. To keep the dynamic program as simple as possible, we add further edges to triangulate {$\bar G$}, resulting in a dual graph and dual spanning tree, {$T^*$}, that is degree 3. We add an artificial root node connected to the node of {$T^*$} corresponding to the outer face of {$\bar G$}.

The dynamic program

For a non-tree edge {$e$}, let {$C_e$} be the elementary cycle formed by {$e$} and the path in {$T$} between the endpoints of {$e$}. Let {$G[C_e]$} be the subgraph of {$G$} that is enclosed by {$C_e$}. We create a dynamic programming table {$DP_e$} that is indexed by every independent set {$S$} of vertices of {$C_e$}. {$DP_e[S]$} is the weight of the maximum-weight independent set of {$G[C_e]$} that includes {$S$}. For subsets {$S' \subset V(C_e)$} that are not independent, we

The dynamic program fills in the tables in a leaf-to-root order. For a leaf edge {$e$}, {$C_e$} is a cycle of length 3 and independent sets of vertices of {$C_e$} can contain at most one vertex. {$DP_e[S]$} is trivial to compute for leaf edges.

200px|thumb|right|A non-leaf, dual-tree edge e and the child edges considered by the dynamic program.? A non-leaf edge {$e$} has at most two child edges {$e_L$} and {$e_R$}. We only detail the case when {$e$} has exactly two child edges; the case of one child edge is simpler. {$C_{e_L}$} and {$C_{e_R}$} are enclosed by {$C_e$}. In fact, it is easy to show that these cycles take the form {$C_e = e \cup P_L \cup P_R,\, C_{e_L} = e_L \cup P_L \cup P_C,\, C_{e_R} = e_R \cup P_C \cup P_R$}, where {$P_L,\, P_R,\, P_C$} are tree paths from a common node {$x$} to the endpoints of {$e_L$} and {$e_R$}.

To populate the entries of the table {$DP_e$}, we consider combining every pair of entries in the child tables {$DP_{e_L}[S_L], DP_{e_R}[S_R]$}. Formally, we populate the entries of the table {$DP_e$} as follows:

 {$DP_e[S] = -\infty\mbox{, for every }S \subseteq V(C_e)$} % initialize the table entries to indicate infeasibility
 {$\mbox{for every } S_L \subseteq V(C_{e_L})$}
     {$\mbox{for every } S_R \subseteq V(C_{e_R})$}
         {$\mbox{if }S_L \cap V(P_C) = S_R \cap V(P_C)$}  % if the two subsolutions are consistent with eachother
             % find the set of vertices that are in e's elementary cycle
             {$\mbox{if }S = S_L \cup S_R \setminus V(P_C)\mbox{ is independent in the original graph}$}
             % original graph is without the edges added to triangulate, etc.
             % note it is sufficient to check if e's endpoints are both in S if e is in the original graph
             % take this solution if it is better than any already computed:
                 {$DP_e[S] = \max\{DP_e[S], DP_{e_L}[S_L]+DP_{e_R}[S_R]-w(S_L \cap V(P_C))\}$}

The root edge {$e_0$} of the dual tree is a convenient representation of the entire graph; the value of the optimal solution is given by {$\max_{S \subset V} DP_{e_0}[S]$}. The usual techniques can be used to compute the independent set corresponding to this value.

Running time

By the above claim, the longest path in {$T$} has at most {$2k+1$} nodes. So, the size of any vertex set that indexes the dynamic programming tables is also at most {$2k+1$}; it follows that the number of entries in {$DP_e$} is at most {$2^{2k+1}$}. One iteration of the innermost loop takes O(k) time. Since the dual tree has a linear number of nodes, the entire dynamic program takes time {$O(k4^kn)$}).

Questions

How would you modify the above algorithm to give a {$(1+\epsilon)$}-approximation for the minimum-cost vertex cover problem? You may assume that minimum-cost vertex cover can be solved in {$2^{O(tw)} n$} time in graphs of treewidth {$tw$}. Be careful: how do you choose the layers so that you are guaranteed to find a feasible solution?
Give a dynamic program for solving the minimum-cost vertex cover problem in {$k$}-innerplanar graphs.

Notes

[^#^]