# Understanding bounded-diameter decomposition of graphs for PTAS

While trying to understand Baker's approach (also explained in this article by Eppstein) to designing PTAS's for planar graphs, I came across a difficulty.

The idea is, given an integer $k$, decompose the graph into subgraphs of tree-width bounded by $O(k)$ (which for planar graphs happens if $diameter = O(k)$), then solve the problem on the subgraphs in polynomial-time, and finally glue the solutions together to get a polynomial-time $(1 + O(1/k))$-approx.

The decomposition method described in the part $8$ of the article, amounts to, as far as I understood, pick any vertex, get a BFS tree from that vertex, and remove every $k$-th level of the tree (potentially starting at level $0 \leq i < k$, but I do not think it matters for this part).

The author then argues that the obtained subgraphs (consisting each of at most $k-1$ levels of the BFS tree), have bounded diameter (i.e. depending only on $k$).

This is the part I do not understand. For instance, what happens if some layer of the tree is a long path ? How is the diameter of a subgraph containing this layer bounded ?

Thank you for any help,

Lucas

-
This is actually Brenda Baker's approach, not mine. The parts I did were to use it for subgraph isomorphism rather than approximation, and to extend it to any apex-minor-free graph family. – David Eppstein Nov 8 '12 at 3:38
This is (obviously) right. I edited my post to clarify things. However, I found that the decomposition scheme presented in your article (or at least the way it is presented) was easier to approach than the decomposition in $k$-outerplanar graphs presented in Baker's article. – beauby Nov 8 '12 at 4:26
I don't remember all the details in this approach but I could recall nor find that they claim the subgraphs have bounded diameter. I thought it says: The graph induced by the vertices in any k consecutive layers (say i to i+k) found by a BFS has tree-width $O(k)$. This is easily seen if one contract all the vertices in early (i.e. layers 1 to i) then the graph has bounded diameter, hence bounded tree-width. – Martin Vatshelle Nov 11 '12 at 6:13

Actually, the obtained subgraphs may not have bounded diameter, but they still have bounded tree-width. In order to see this, take one such subgraph $H$, and build $H'$ by adding a new vertex $u$ that is connected to each of the top-level vertices of $H$ (remember that $H$ was obtained as $k-1$ consecutive layers of a BFS tree). Then clearly $diam(H') \leq 2k$ since any vertex in $H'$ is at distance less than $k$ of $u$. We then know that $tw(H') = O(diam(H')) = O(k)$. Finally, $H$ is a minor of $H'$ so $tw(H) \leq tw(H')$, hence $tw(H) = O(k)$.
Yes, that's basically it. Instead of adding a new vertex to form $H'$, you could view it as a minor of the original graph, formed by contracting all the earlier BFS levels. – David Eppstein Nov 8 '12 at 6:24