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 ...
- 50.8k
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-...
- 71
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}...
- 8,588
5
votes
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, ...
- 9,595
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 ...
- 1,306
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 ...
- 1,419
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\}$.
...
- 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 ...
- 1,642
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-...
- 151
3
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 ...
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 ...
- 2,758
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,...
- 9,595
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 ...
- 50.8k
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 ...
- 11.6k
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 ...
- 2,560
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, \...
- 9,595
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,762
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible