Questions tagged [set-cover]

Set cover is a well-known NP-complete problem: given a collection of sets, find as small as possible a subcollection whose union is the same as the union of the entire collection.

Filter by
Sorted by
Tagged with
16
votes
1answer
236 views

Transforming an arbitrary cover into a vertex cover

Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained ...
15
votes
1answer
769 views

Grid covering by rectangles

We have a $N_1 \times N_2$ grid. We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those ...
11
votes
1answer
357 views

Finding a minimal cover of a subset of a finite cartesian product by cartesian products

Given a subset of a cartesian product $I \times J$ of two finite sets, I wish to find a minimal cover of it by sets which are cartesian products themselves. For example, given a product between $I=\{...
10
votes
4answers
1k views

Minimum number of shopping trips for a group of people to buy presents for each other

We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a ...
9
votes
4answers
4k views

What are the real world applications of set cover problem?

I am studying about set cover problem and wondering that which problems in real world can be solved by set cover. I found that IBM used this problem for their anti-virus problem, so there should be ...
9
votes
1answer
525 views

Hardness of approximating Minimum Cardinality Exact Cover

The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint. Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for ...
7
votes
2answers
8k views

Algorithm to return largest subset of non-intersecting intervals

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals. i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...
7
votes
1answer
1k views

Proving NP-hardness of strange graph partition problem

I am trying to show the following problem is NP-hard. Inputs: Integer $e$, and connected, undirected graph $G=(V,E)$, a vertex-weighted graph Output: Partition of $G$, $G_p=(V,E_p)$ obtained ...
6
votes
2answers
126 views

Minimum set cover with incompatible sets

I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously). To state it more formally: We have a finite base set $X$ and a family $\...
6
votes
1answer
65 views

Hardness of a problem related to set cover

Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times ...
6
votes
1answer
376 views

Time Complexity of a selection problem

I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem. [Assuming operations on integers take $O(1)$ time] We are Given $m$ sets, ...
5
votes
1answer
413 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
5
votes
1answer
2k views

Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers

I have the following problem, which seems to be similar to Set Cover. We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S$ of subsets (e.g., $S=\{\{1\...
5
votes
0answers
87 views

Specialized Algorithm for Set-Cover with $k=3$

I know that the Set-cover problem with $n$ elements and a universe of size $N$ is NP complete. Also, the problem is has parameterized complexity regarding the number of sets $k$ that should cover the ...
4
votes
1answer
185 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq \...
4
votes
1answer
50 views

Probability of randomly designated subsets cover the universe

Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$. Is there a polynomial ...
4
votes
1answer
152 views

Path cover with paths of bounded length, in the plane

I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$. I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the ...
3
votes
1answer
175 views

maximum coverage version of dominating set

The dominating set problem is : Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
3
votes
1answer
322 views

Is 'double max-$k$ vertex-cover' NP-hard?

Consider the following problem, which I have called '$\mathsf{\text{double max $k$-vertex-cover}}$': Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices ...
3
votes
1answer
243 views

Clarification on the inapproximability of set cover

I'm trying to understand the inapproximability of the minimum set cover problem. The wikipedia page states that it is hard to approximate within a factor of $(1-o(1))\ln n$ and that $n$ refers to the ...
3
votes
2answers
746 views

Is greedy algorithm the best algorithm for set cover problem?

Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem. I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+...
3
votes
1answer
1k views

Greedy algorithm for Set Cover problem - need help with approximation

I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above. ...
3
votes
1answer
112 views

Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory"

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...
3
votes
1answer
120 views

Is this variation of set-cover NP-hard to approximate?

The classic set-cover problem is described as follows: Let $S = \{s_1, ..., s_n\}$ be a target set, and let $\Lambda = \{A_1, ..., A_m: A_i \subset S\}$ be a collection of subsets of $S$. The ...
3
votes
1answer
212 views

NP-hardness of maximum set cover with even/odd coverage requirement

Given universal set $U=X \cup Y = \{x_1, \ldots, x_{n_1} \} \cup \{y_1, \ldots, y_{n_2}\}$ where $X \cap Y = \emptyset$ and sets $\mathcal{S}=\{s_1, \ldots, s_m\}$ such that $s_i \subseteq U$ for all $...
3
votes
1answer
129 views

Maximum coverage 1/2-approximation algorithm: why does the central lemma hold?

I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that ...
3
votes
1answer
90 views

Upper bound for size of minimal covers of a set

Would appreciate any insight about the following regarding set covers: Begin with a universe set $X = \{x_1,x_2,...,x_n\}$ and a set $S=\{s_1, s_2,...,s_p\}$ such that each $s_i \subseteq X$ and $\...
3
votes
1answer
711 views

Hitting Set Problem with non-minimal Greedy Algorithm

The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ ...
3
votes
1answer
69 views

Clarification on NP-hardness and hardness of approximation results for set cover?

I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements. I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it ...
3
votes
1answer
3k views

Given a set of intervals on the real line, find a minimum set of points that "cover" all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
3
votes
1answer
32 views

Hardness of approximation statement clarification?

In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved ...
3
votes
1answer
2k views

Every vertex cover is a dominating set

Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set. Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)...
3
votes
0answers
44 views

Weighted Set Cover Problem Minimizing Average Weight

In the traditional weighted set cover problem, we aim at minimizing the sum of the weight of the selected sets. Is there any problem/literature that aim at minimizing the average weight of the ...
3
votes
0answers
185 views

2-approximation edge-cover algorithm using primal-dual method

The problem Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle. So far I managed to represent the ...
2
votes
2answers
49 views

Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

I am trying to solve the Budgeted Maximum Coverage Problem. I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller. Both are approximation algorithms. ...
2
votes
2answers
136 views

Approximation of Set Cover

I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better ...
2
votes
2answers
44 views

Growing a set given constraints

I am trying to solve the following: Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to: $\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = ...
2
votes
1answer
852 views

Set cover problem with constant size subset

Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?
2
votes
1answer
312 views

Is this variant of set cover NP-complete?

Let's say we have a universe $U$ of $n$ elements and a collection $S$ of $m$ subsets of $U$, i.e., $S=\{S_1,\ldots,S_m\}$, and a positive integer $k$. If I ask "is there a set cover of $U$ of size $k$ ...
2
votes
1answer
67 views

Solution to a Np-hard problem and its relevance to a dual LP

From The design of APX algorithms book by David P. Williamson and David B. Shmoys, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual): Let $y^*$ be ...
2
votes
1answer
100 views

Is this a known problem in graph theory?

My basic problem includes a graph where each node $i$ is associated with a weight $c_i$, and the problem is to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$. This ...
2
votes
1answer
203 views

Approximation algorithm for weighted set cover, using multiplicative weights

It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
2
votes
1answer
60 views

How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there ...
2
votes
1answer
224 views

An exact solution for biclique vertex-cover problem on a bipartite graph

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs). It has been shown that "Biclique Vertex-...
2
votes
1answer
324 views

Approaches to the size constrained weighted set cover problem

I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended ...
2
votes
1answer
67 views

Minimum number of sets of points

During my work I've encountered this problem: $G = \{(x_i,y_i,z_i)\}_{i=1}^{n}$ is a group of points in space ($\forall i \;\; x_i,y_i,z_i \in \Bbb R$) and $ d \in \Bbb R^+$ is a constant. Divide $...
2
votes
1answer
122 views

I want to figure out whether my problem described below is reducible to the set cover problem

I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$. I need an algorithm that gives me a set $T$ of minimum cardinality ($T \...
2
votes
1answer
84 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
2
votes
1answer
596 views

Finding an instance of an n-element set cover

Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter ...
2
votes
1answer
147 views

Enumerating all set covers when knowing one set at least

I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$. Then I have a query $Q=(s, k)$, where $s \in P(S) - \{\emptyset \cup S\}$ and $ 1 < k \...