6
$\begingroup$

I was wondering about the complexity of the following covering problem. Let $B_i,\,i=1,\ldots,n$ be a set of unit disks in $\mathbb{R}^2$. The problem is to decide whether there exists $C\subset\{1,\ldots,n\}$ with $|C|\leq k$ such that $\bigcup_{i\in C} B_i = \bigcup_{i=1}^n B_i$. This could be considered as a continuous version of the geometric set cover problem.

There is a paper that provides a constant approximation algorithm (Basappa et al, "Unit disk cover problem in 2D") but no proof of NP completeness has been provided. In this paper, the problem is referred to as the "rectangular region cover" problem. Also, in one version of the paper, they claim that the problem is NP-complete and they refer to Garey & Johnson but I could not find a proof there either. Computational complexity is far to my area of expertise so I do not want to reinvent the wheel by reproducing some well-known result. Any help will be greatly appreciated.

$\endgroup$
2
  • $\begingroup$ Do they refer to anything specific in Garey & Johnson? $\endgroup$ – Gerry Myerson Aug 31 '19 at 2:02
  • 1
    $\begingroup$ @GerryMyerson The quote "Unfortunately, both the DUDC and RRC problems are also NP-complete [Garey&Johnson], ..." appears in the ArXiv version arxiv.org/pdf/1209.2951.pdf $\endgroup$ – Mike Anonymous Aug 31 '19 at 5:21
4
$\begingroup$

The typical presentation of this problem is more like the following:

Given: A finite set of points $P$ and a set of unit disks $C$ in the plane

Question: Does there exist a subset $C' \subseteq C$ such that $|C'| \leq k$ and $P \subseteq \cup_{S \in C'} S$?

In this formulation, this problem is commonly known as DISCRETE UNION DISK COVER (DUDC). I believe the canonical reference for demonstrating that this problem is NP-complete is [1].

Note that in DUDC, $P$, the set of points to be covered, is given as finite. In the version proposed in this question, the set of points to be covered is given as $\cup_{S\in C} S$. In order to show that this version is NP-complete, we will need to demonstrate how some known NP-complete problem (either DUDC or otherwise) can be translated into this version. [A previous version of this answer had the conversion the wrong way around.]

EDITED TO ADD:

One other problem that seems related but not quite on the nose is DOMINATING SET IN DISK GRAPHS. It can be paraphrased as follows:

Given: A set of unit disks $C$ in the plane

Question: Does there exist a subset $C' \subseteq C$ such that $|C'| \leq k$ and for each $c \in C$ there exists $c' \in C'$ such that $c'$ intersects $c$?

I believe the original reference for the NP-completeness of this problem is [2] where it is referred to as "EUCLIDEAN m-CENTER ON POINTS".

  1. Fowler, Robert J., Michael S. Paterson, and Steven L. Tanimoto. "Optimal packing and covering in the plane are NP-complete." Information processing letters 12.3 (1981): 133-137

  2. Masuyama, Shigeru, Toshihide Ibaraki, and Toshiharu Hasegawa. "The computational complexity of the m-center problems on the plane." IEICE TRANSACTIONS (1976-1990) 64.2 (1981): 57-64.

$\endgroup$
5
  • $\begingroup$ I actually had this exact idea in mind, but then left it as I thought it will not work. My reasoning was follows: Consider two unit disks: one with center at the origin $(0,0)$ and the other at $(1,0)$. Obviously, both disks are needed for full coverage. There are three sectors. If you choose the sector representative points as $(-\epsilon,0)$, $(0.5,0)$, and $(1+\epsilon,0)$, then you just need one disk to cover all three points. The two problems are thus not equivalent. $\endgroup$ – Mike Anonymous Aug 30 '19 at 23:33
  • $\begingroup$ Hmm nevermind, I think I am confused... Let me think a little more. $\endgroup$ – Mike Anonymous Aug 30 '19 at 23:35
  • $\begingroup$ I think the gap in this argument is as follows (correct me if I am wrong): Yes, sure in this way I can transform my problem to an instance of DUDC. But this particular instance of DUDC may be solved in polynomial time because it corresponds to a specific arrangement of points and covering disks. We need an argument in the other way around: Transform an instance of DUDC to our problem, which does not seem possible with the argument you have provided. $\endgroup$ – Mike Anonymous Aug 30 '19 at 23:42
  • $\begingroup$ @MikeAnonymous Ah! You are absolutely correct. I've made the most common error in NP-completeness analysis. I will edit the answer to reflect this. $\endgroup$ – mhum Aug 30 '19 at 23:45
  • $\begingroup$ I myself had wished the argument worked that way. I really appreciate your help regardless. I guess there is no easy escape but to suffer through some nasty construction :) $\endgroup$ – Mike Anonymous Aug 30 '19 at 23:52

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.