# Tag Info

10

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 edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a ...

9

The Lovász $\vartheta$ function is an efficiently computable function with the property $$\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G),$$ where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have ...

7

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-Completeness by Garey and Johnson. The NP-completeness of it was proved by Stockmeyer.

7

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. In fact, "Exact Cover" is contained in W[1]. It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]: ...

6

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$ with $n$ vertices, and a number $k$, and the question is whether the graph $G$ has an independent set of size $k$. We assume that $k$ is large (say, polynomial in ...

6

If the required number of times we need to cover an element is 2, we have the following densest k-subgraph problem: (Imagine the edges are elements and nodes are sets.) Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum density. Khot proved that no PTAS exists under plausible complexity assumptions; there is an $O(n^{1/... 5 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}(f(P_i))>\mathrm{Vol}(P_i)$, so no need to cut into several pieces. Banach-Tarski works because the notion of volume is not well-defined on the pieces. ... 5 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 THREE SETS (X3C): Instance: Set$X=\{x_1,x_2,...,x_{3q}\}$and a collection$C=\{C_1,...,C_m\}$of 3-element subsets of$X$. Question: Does C contain an exact ... 5 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 and D. Peleg, Generalized submodular cover problems and applications, Theoretical Computer Science, 250:179-200, 2001. 5 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 out that Hitting Set is W[1]-hard already when the VC-dimension is equal to 2. 4 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 heuristic is picking the set which greedily increases the solution profit, you might end up in a lousy approximation ratio. Consider the following example: $$A = \{... 4 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 n<m. Let U=\cup_i (A_i\cup B_i\cup Z_i) where all sets in the union are completely disjoint. In fact, A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\} and ... 4 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\}. Assume we want to cover U with the sets C=\{S_1,\ldots,S_n,U\}, where c(U)=2, c(S_i)=1. We would now start with C ans see that the effectivity of the sets ... 4 (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 the number of elements in A that are double covered by X, i.e. |A \cap \left(\bigcup(X \setminus \{A\})\right|. Additionally, let c(X) denote the number ... 4 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 lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's ... 3 ...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-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p 2 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_is) is NP-hard. We will refer to this decision problem as the Numerical Trident Cover Problem. To prove that the Numerical Trident Cover Problem is NP-hard, we introduce the following ... 2 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,k) obtained by taking the union of n independent copies of (F,U,k) (where the ith copy of F uses the ith copy of U as its base set) is equivalent, ... 2 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 to it is "The Positive-Negative Partial Set Cover problem". To question 2: Although the adapted trivial heuristic (each time picking the set which greedily ... 2 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}{L}\right)^2$$Therefore the chance that it is not covered by any set is:$$\left(1-\left(\frac{a}{L}\right)^2\right)^N$$Using the union bound, the chance ... 2 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 follows that it is NP-complete. 2 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 wikipedia page. 2 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 shown in [2], in which given a 3SAT instance, one can construct a universe U=\{1,\dots,N\} and a set S of 3-sets such that there is an exact cover of U (i.e ... 2 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 you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in ... 2 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, \mathcal S, E) where$$E=\{(u, S)\in U\times\mathcal S : u\in S\}.$$Make the weight of u equal to its cost and the weight of S equal to its profit. Then a ... 1 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\},~ S_2-\{a\}.$$Do the same for all other pairs of consecutive sets. The resulting instance satisfies your condition, and it is equivalent (with respect to ... 1 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 graphs succinctly defined using CNF formulas to the problem that I have described. The dominant set problem is known to be NExpTime complete [1] for graph ... 1 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 cheaply as possible. At each step, the algorithm adds the set$S_i$for which$\frac{w_i}{|\hat{S}_i|}$is lowest, where$\hat{S}_i$is the subset of$S_i\$ which ...

1

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 from the instance). This is the well-known greedy algorithm for the "Interval Point Cover" problem; see for instance the course page by Andranik Mirzaian for a ...

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