The 2024 Developer Survey results are live! See the results

Tag Info

Minimal generator for a set of sets

A decision variant, without the minimality condition, asking whether there is a set $B$ of size $n$ is called the set basis problem [SP7] in Computers and Intractability: A Guide to the Theory of NP-...
• 71
Accepted

Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, ...
• 10.8k

• 148

Known Variant of Set Cover?

We can abstract this problem as submodular minimization (minimize additional covers) under submodular cover (set cover) constraint. I'll point you towards two papers in this area. Iwata and Nagano, ...

Covering a binary relation as a union of rectangles

...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions. Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-...
• 151

Set cover with small subsets

Set cover for $d=2$ is the edge cover problem, which is a poly-time problem [1]. For $d=3$, it is indeed NP-complete. This can be shown using the same reduction from 3SAT to 3-dimensional matching ...

Restricted Universe Exact Cover

RestrictedExactCover is at least as hard as ExactCover, as ExactCover is a special case of RestrictedExactCover (the special case where $U=U'$). Also, clearly RestrictedExactCover is in NP. It ...
• 12.3k
Accepted

Definition of k-set cover

The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements. You can find more information on the ...
• 2,559

• 10.8k
Accepted

Set Cover with Multiple covers

This answer expands on Chandra's comment. We'll prove two lemmas that show that $q=O(\log m)$ is a necessary condition for Properties (1) and (2) to hold, and that this bound is tight in the sense ...
• 10.8k

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time ...
• 51.1k
1 vote
Accepted

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

Lemma 1. The problem is NP-hard. Proof. By reduction from Clique. Given an instance $(G=(V,E), k)$ of Clique (with $k<|V|$), the reduction produces the instance of OP's problem defined as follows. ...
• 10.8k
1 vote
Accepted

Set cover where consecutive sets differ by at most one item

Take an arbitrary instance $S_1,\ldots,S_n$ of SET COVER. Between $S_1$ and $S_2$, insert a chain of new subsets  S_1-x,~ S_1-\{x,y\},~ \ldots,~ \{z\},~ \emptyset,~ \{c\},~ \ldots,~ S_2-\{a,b\},~ ...
• 5,782
1 vote

CNF encoding of set cover - NExpTime-completness

As I suspected in my question, they are useful results in the literature that can be exploited to characterize the complexity of the problem. There is a reduction from the dominant set problem for ...

Only top scored, non community-wiki answers of a minimum length are eligible