Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 6 down vote favorite
1

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

share|improve this question
2  
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
1  
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

1 Answer

up vote 4 down vote accepted

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)$.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.