<p>In a single layer of the partition, consisting of the vertices at distance $d$ to $d+k$ from the root, the vertices at distance $d+1$ through $d+k-1$ can be dominated the same way as they are in the whole graph, but you have no control of the size of the dominating sets of the vertices at distances $d$ or $d+k$, on the boundary of the layer: in the original graph, those vertices could be dominated by a small number of vertices in a different layer that aren't there when you restrict to that layer. So the solution is to find a system of layers with the property that the subsets of vertices at distance $d+1$ through $d+k-1$ within each layer form a partition of the whole graph, and then within each layer to only try to dominate that subset. To do this, you need to overlap the layers by two levels.</p>

CC BY-SA 3.0
2013-05-30T07:13:25.153Z
2013-05-30T07:22:57.967Z
2013-05-30T07:22:57.967Z
David Eppstein
<p>(I'm not sure if this is an appropriate question for TCS.SE, but I'm not sure what is more appropriate).</p>

<p>When using Baker's Technique to find an approximation to the minimum dominating set of a planar graph, why must we overlap <em>2</em> BFS layers in every partition? I understand that for vertex cover each partition needs to overlap 1 layer to handle cases where an edge in the overlapped layer can only be covered by another vertex in the layer. </p>

<p>However, to my knowledge, vertex cover is just a reduction of dominating set, and any vertex cover is also a dominating set. Why do we need to overlap 2 layers for dominating set?</p>

<p>Of course, links to papers are great too--I just haven't found anything explaining the reason yet.</p>

<p><strong>EDIT:</strong> David has a great answer below. There's also a paper describing the issue (with pictures) and a correction to Baker's original algorithm for Dominating Set here: <a href="http://www.mdpi.com/1999-4893/6/1/43" rel="nofollow">http://www.mdpi.com/1999-4893/6/1/43</a> (<a href="http://www.mdpi.com/1999-4893/6/1/43/pdf" rel="nofollow">PDF link</a>)</p>

<graph-theory><planar-graphs>
Overlapping BFS Layers in Dominating Set with Baker's Technique
Taj Morton
# Overlapping BFS Layers in Dominating Set with Baker's Technique

(Asked by: username_0 on 2013-05-30)

(I'm not sure if this is an appropriate question for TCS.SE, but I'm not sure what is more appropriate).

When using Baker's Technique to find an approximation to the minimum dominating set of a planar graph, why must we overlap *2* BFS layers in every partition? I understand that for vertex cover each partition needs to overlap 1 layer to handle cases where an edge in the overlapped layer can only be covered by another vertex in the layer.

However, to my knowledge, vertex cover is just a reduction of dominating set, and any vertex cover is also a dominating set. Why do we need to overlap 2 layers for dominating set?

Of course, links to papers are great too--I just haven't found anything explaining the reason yet.

**EDIT:** David has a great answer below. There's also a paper describing the issue (with pictures) and a correction to Baker's original algorithm for Dominating Set here: <http://www.mdpi.com/1999-4893/6/1/43> ([PDF link](http://www.mdpi.com/1999-4893/6/1/43/pdf))

**Tags:** graph-theory, planar-graphs

---

## 1 answers

### Answer by username_1 on 2013-05-30. Score: 8 | Accepted answer

In a single layer of the partition, consisting of the vertices at distance $d$ to $d+k$ from the root, the vertices at distance $d+1$ through $d+k-1$ can be dominated the same way as they are in the whole graph, but you have no control of the size of the dominating sets of the vertices at distances $d$ or $d+k$, on the boundary of the layer: in the original graph, those vertices could be dominated by a small number of vertices in a different layer that aren't there when you restrict to that layer. So the solution is to find a system of layers with the property that the subsets of vertices at distance $d+1$ through $d+k-1$ within each layer form a partition of the whole graph, and then within each layer to only try to dominate that subset. To do this, you need to overlap the layers by two levels.


---

