I come to you with a problem I have been struggling with for the past few weeks. I would like to classify (complexity) a special case of Unique Coverage. To set the mood on, I will start by introducing the Exact Set Cover and Unique Coverage problems. I will then go over the special cases I am interested in.

Set covering problems come in a wide variety of variants. The classical decision problem Exact Set Cover consists in, given a ground set $\mathcal{U}$ and a set of subsets $S\subset \mathcal{P}(\mathcal{U})$, deciding whether there exists $S'\subset S$ of cardinality such that every element of $\mathcal U$ is covered by at exactly one set in $S'$. This problem has been extensively researched, and not suprisingly classified as NP-complete (NPC).

Unique Coverage is a natural optimization variant of the Exact Set Cover problem. In this problem, the input is the same as before $(\mathcal{U},S\subset \mathcal{P}(\mathcal{U}))$ but the goal is now to find $S'\subset S$ maximizing the number of elements from $\mathcal{U}$ which are covered exactly. Obviously, Unique Coverage is harder than Exact Set Cover since an instance of the latter is positive if and only if the former admits a solution covering $|\mathcal U|$ elements. Exact Set Cover being NPC, the decision variant of Unique Coverage is NPC as well.

Geometrical variants of the Unique Coverage problem have been studied as well. In a geometrical setting, the ground set $\mathcal U$ is assumed to be a set of points in a space, and the subsets of $\mathcal U$ are induced by geometrical objects (polyhedrons, balls, whatever).

Above line ends the introduction on exact set cover and unique coverage. My questions follow

Erlebach and van Leeuwen [1] prove Unique Coverage to be NP-hard for unit disks in the plane. I am wondering whether the problem stays hard in the following even-more-special cases.

  1. The unit disks are all centred in the same disk $D$ and the points to cover lie outside $D$.
  2. The points to cover all lie in a connected area $Z$ such that two disks intersect at most once in $Z$.
  3. The combination of the two cases above.

At first I was fairly confident the first two cases were hard. Then I found two articles.

Chan et al. [2] results on sets of pseudo-disks can be used to prove that the Exact Set Cover is polynomial in case (1). Baysan et al. [3] show that the classical Set Cover problem in case (1) is polynomially solvable.

Their results kind of convinced me that the special cases I am considering are in fact easy to solve. Yet, I haven't managed to prove it and am running out of steam. Thus this post, to exchange on the subject (if you think of any paper vaguely related to the problem, or you have worked on similar settings...)

Thank you very much if you read this far.


[1] T. Erlebach and E. J. van Leeuwenn. Approximating Geometric Coverage Problems. 2008

[2] T. Chan and E. Grant. Exact Algorithms and APX-Hardness Results For Geometric Packing and Covering Problems. 2014

[3] A Polynomial Time Solution to Minimum Forwarding Set Problem in Wireless Networks under Unit Disk Coverage Model. 2008

  • $\begingroup$ Welcome to CS.SE! Interesting question. Thanks for all the background! Can you summarize the main idea(s) of [2] and [3]? Is it easy to concisely summarize their main idea/approach, or is it more complicated? $\endgroup$ – D.W. Jul 2 '17 at 15:21

Your Answer

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

Browse other questions tagged or ask your own question.