10
$\begingroup$

Given a finite set $X$ and a collection $F$ of subsets of $X$, we define a cover of $X$ in $F$ as a subset of $F$ whose union is equal to $X$. A cover $C$ of $X$ in $F$ is said to be exact if the sets in $C$ are pairwise disjoint.

In this question, we are interested in the case where every set in $F$ has the same size $k$, and moreover, $X$ can be partitioned into $k$ disjoint subsets $X_1, \ldots, X_k$ of equal size so that every set in $F$ contains exactly one element in $X_i$ for each $1 \le i \le k$.

For a nondecreasing function $r : \mathbb{N} \to [1, \infty)$, consider the following promise problem.

Gap Multi-Dimensional Cover (with a parameter $r(n)$)
Instance: $k$, $m \in \mathbb{N}$, $k$ pairwise disjoint sets $X_1, \ldots, X_k$ each of size $m$, and a collection $F$ of subsets of $X = X_1 \cup \cdots \cup X_k$ such that every set $E \in F$ contains exactly one element in $X_i$ for each $1 \le i \le k$.
Yes-promise: $F$ has an exact cover of $X$ (that is, a cover of size $m$).
No-promise: Any cover $C$ of $X$ in $F$ satisfies $|C| > m \cdot r(k m)$.

(Note that larger values of the function $r(n)$ means an easier problem.)

The problem is clearly in NP for any choice of the function $r(n)$. As for the hardness, it is easy to see that in the gapless case (that is, $r(n) = 1$ for all $n$), the problem is NP-complete (even if $k$ is fixed to 3) because it contains 3-Dimensional Matching as a special case. The following stronger result is a corollary of Theorem 4.4 of [Pet94]: there exists a constant $r > 1$ such that Gap Multi-Dimensional Cover with parameter $r$ is NP-complete (even if $k$ is fixed to 3).

Note that the optimization version of Multi-Dimensional Cover (where the task is to find a cover of minimum cardinality) can be naturally defined, and it is a special case of $k$-Set Cover. Gap Multi-Dimensional Cover with parameter $r(n)$ is not harder than approximating Multi-Dimensional Cover within a factor of $r(k m)$, which is in turn not harder than approximating $k$-Set Cover within a factor of $r(k m)$.

If $r(n) \ge \ln n - \ln \ln n + 0.78$, the problem is in P by using the greedy algorithm [Sla97]. (The case where $r(n) \ge \ln n - O(1)$ is much easier and has been long known [Joh74].)

Questions

Although inapproximability of Set Cover is studied very well, the above special case does not seem to be particularly well-studied, at least explicitly. Therefore, any hardness results about this special case would be interesting.

Other than what is stated above, what can be said about the hardness of Gap Multi-Dimensional Cover under a plausible assumption? For example, are the following statements true?

  1. “For every constant $r \ge 1$, Gap Multi-Dimensional Cover with parameter $r$ is NP-complete.”
  2. “Gap Multi-Dimensional Cover with parameter $r(n) = (1 - \varepsilon) \ln n$ is not in P for any constant $0 < \varepsilon < 1$ unless NP $\subseteq$ DTIME($n^{\log \log n}$).”

If they are true, they will immediately imply the following two known inapproximability results for Set Cover, respectively (therefore the above two results will be refinements of the below two):

  1. For every constant $r \ge 1$, it is NP-hard to approximate Set Cover within a factor of $r$ [BGLR93].
  2. For every constant $0 < \varepsilon < 1$, Set Cover cannot be approximated within a factor of $(1 - \varepsilon) \ln n$ in polynomial time unless NP $\subseteq$ DTIME($n^{\log \log n}$) [Fei98].

Therefore, I am interested in whether the hardness of Gap Multi-Dimensional Cover can be obtained as corollaries of the results of [BGLR93] and [Fei98] or their proofs.

I am also interested in other hardness results on Gap Multi-Dimensional Cover. For example, it is interesting to see whether other results about inapproximability of Set Cover (e.g. [RS97, AMS06] and there are probably many more) can be refined to say anything about hardness of Gap Multi-Dimensional Cover.

Application

This question is motivated by a question “Set Cover for Permutation Matrices” by Brayden Ware, where he asks about approximability of a special case of Set Cover. An answer which I posted in response to that question can be viewed as a reduction from Set Cover to the optimization version of Multi-Dimensional Cover (with $m = 2$) followed by a reduction from Multi-Dimensional Cover to Set Cover for Permutation Matrices.

Related to that question, I considered the following question out of curiosity. Any solution to Set Cover for Permutation Matrices must have size at least $n$. Therefore, an instance of Set Cover for Permutation Matrices can be thought of as the “best case” if it has a cover of size $n$ (in which case it is an exact cover). Is it still hard to distinguish these “best cases” from the cases which are “far from the best”?

If I am not mistaken, an affirmative answer to the current question (under some assumption) will imply that in Set Cover for Permutation Matrices, it is impossible (under the same assumption) to distinguish the instances which have a cover of size $n$ from the instances whose cover has size larger than $n \cdot r(n)$.

References

[AMS06] Noga Alon, Dana Moshkovitz and Shmuel Safra. Algorithmic construction of sets for $k$-restrictions. ACM Transactions on Algorithms, 2(2):153–177, April 2006. http://dx.doi.org/10.1145/1150334.1150336

[BGLR93] M. Bellare, S. Goldwasser, C. Lund and A. Russell. Efficient probabilistically checkable proofs and applications to approximations. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pp. 294–304, May 1993. http://dx.doi.org/10.1145/167088.167174

[Fei98] Uriel Feige. A threshold of ln $n$ for approximating set cover. Journal of the ACM, 45(4):634–652, July 1998. http://dx.doi.org/10.1145/285055.285059

[Joh74] David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256–278, Dec. 1974. http://dx.doi.org/10.1016/S0022-0000(74)80044-9

[Pet94] Erez Petrank. The hardness of approximation: Gap location. Computational Complexity, 4(2):133–157, April 1994. http://dx.doi.org/10.1007/BF01202286

[RS97] Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pp. 475–484, May 1997. http://dx.doi.org/10.1145/258533.258641

[Sla97] Petr Slavík. A tight analysis of the greedy algorithm for set cover. Journal of Algorithms, 25(2):237–254, Nov. 1997. http://dx.doi.org/10.1006/jagm.1997.0887

$\endgroup$

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.