5
$\begingroup$

(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)

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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