It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.

However, it seems that this specific approach does not lead to a PTAS for the MINIMUM DOMINATING SET problem (MDS), whereas other approaches do, see E. D. Demaine and M. Hajiaghayi: Approximation Schemes for Planar Graph Problems (1983, 1984; Baker).

In T. Nieberg and J. Hurink: A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs (also accessible here), the authors define the notion of 2-separated sets, that is, a collection of subsets of vertices of a graph such that two vertices from different sets are at distance at least two from each other. If a graph admits such a set (with additional suitable properties), they prove that MDS admits a PTAS. This is the case for unit disk graphs for example.

This notion is really similar to the technique of recursive separators in planar graphs, except for the distance-2 requirement. So my question:

Do good (in the sens of usual separators) "distance-2-separators" exist in planar graphs, and if yes, can we compute them efficiently?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.