10 votes
Accepted

Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the ...
user avatar
7 votes

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-...
user avatar
7 votes
Accepted

Parameterized complexity of Exact Cover

Correction: I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods. ...
user avatar
  • 5,712
6 votes
Accepted

Set cover in which some pairs of sets are forbidden

This problem is way harder than set cover. Here is why... Intuitively, you can encode independent set as a problem of this type. Indeed, you are given an instance of independent set - a graph $G$ ...
user avatar
5 votes

Can the Banach-Tarski paradox be "realized" by floating-point round-off?

This seems to have little to do with Banach-Tarski. In your setting, f is simply not an isometry due to floating-point errors, and in particular there must be a single piece $i$ such that $\mathrm{Vol}...
user avatar
  • 7,653
5 votes

Parameterized complexity of Hitting Set in finite VC-dimension

We address this question in a new preprint: http://arxiv.org/abs/1512.00481 Hitting Set in hypergraphs of low VC-dimension (Karl Bringmann, László Kozma, Shay Moran, N.S. Narayanaswamy). It turns ...
user avatar
5 votes

Variation on partial Set Cover with penalties

This answers question (2): The greedy heuristic for Set Cover / Maximum Coverage always picks the set which contains the maximal number of uncovered elements. Assuming your modification for the ...
user avatar
  • 9,378
5 votes

Set Cover with bounded intersection size

If I'm not missing something, you can use a reduction from SINGLE OVERLAP RESTRICTED EXACT COVER BY 3 SETS (SINGLE OVERLAP RX3C) which I proved to be NPC in this cstheory question. EXACT COVER BY ...
user avatar
5 votes

Set cover with budget on sets

Yes, this variant, and in fact a further generalization has been considered in the literature. See the paper below for the problem they call capacitated facility location. J. Bar-Ilan, G. Kortsarz ...
user avatar
4 votes
Accepted

What is the reverse of greedy algorithm for setcover?

The approximation guarantee will be significantly worse. Assume you want to cover the set $U=\{1,\ldots,2n\}$. For every $i=1,\ldots,n$ define a set with n+1 elements by $S_i=\{i,n+1,\ldots,2n\}$. ...
user avatar
  • 56
4 votes
Accepted

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

(Comment $\rightarrow$ Answer) Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$: For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as ...
user avatar
  • 1,624
4 votes

What is this variant of set cover problem known as?

Here I show that the problem is NP-complete. We convert a CNF to an instance of your problem as follows. Suppose that the variables of the CNF are $n$ $x_i$'s and the clauses are $m$ $C_j$'s, where $...
user avatar
  • 13.5k
4 votes
Accepted

Complexity of Finding Optimal Synergistic Set Packings

This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's ...
user avatar
3 votes

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-...
user avatar
2 votes

Variation on partial Set Cover with penalties

Sorry for answering my own question, but I found the answer quite clearly. To question 1: It turns out that this problem has been studied by Pauli Miettinen not too long ago. The intuitive name given ...
user avatar
  • 171
2 votes

NP-hardness of a Set Cover specialization

Overview This problem is NP-hard; more precisely, the associated decision problem (in which we ask whether a target number of tridents $k$ can cover all of the given $x_i$s) is NP-hard. We will refer ...
user avatar
2 votes

Is the following problem NP hard?

Lemma. The problem is NP-hard. Proof sketch. We disregard the constraints $|F_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,...
user avatar
  • 8,143
2 votes
Accepted

Minimum order of partite in a bipartite graph

This is an upper bound on $N$ for the second formulation: Assume that I pick $N$ uniformly random sets. The probability of a pair of elements not to be covered by a specific set is $$1-\left(\frac{a}...
user avatar
  • 9,378
2 votes

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 ...
user avatar
  • 10.4k
2 votes
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 ...
user avatar
  • 2,530
2 votes

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 ...
user avatar
2 votes

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 ...
user avatar
2 votes
Accepted

Set cover with rewards

Seems to be in P, as it seems to be equivalent to max-wt independent set (equivalently min-wt vertex cover) in a bipartite graph, which is in P. Specifically, construct the bipartite graph $G=(U, \...
user avatar
  • 8,143
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\},~ ...
user avatar
  • 5,712
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 ...
user avatar
1 vote

Partial cover approximation

Having discussed with other users, I believe the following answers the question. To begin with let us recap the greedy algorithm for the set cover problem, in which we wish to cover all of $E$ as ...
user avatar
1 vote
Accepted

1-D set cover optimisation with connected subsets

The leftmost point must be covered by some interval. There is no harm in picking the longest interval that covers the leftmost point. Then iterate (after removing the interval and all covered points ...
user avatar
  • 5,712
1 vote
Accepted

Covering by disjoint sets

Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph $G=(V,E)$, define your ground set as $U:=V$ and for every vertex $v\in V$ construct a ...
user avatar
  • 5,712

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