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
1
vote
1answer
597 views

Reverse cartesian product matching all given rows

I´m looking for an efficient algorithm that will find reverse cartesian products. Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \...
1
vote
1answer
403 views

Maximum weighted disjoint set union

I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this ...
1
vote
0answers
41 views

Algorithms for MinSat when all literals are positive?

I am given a set $U = \{1, \cdots, n\}$ and a set of subsets $C_1, \cdots, C_k$ of $U$; here the sets are all the same size. The minimum set-cover problem of course is to find the minimum number of ...
1
vote
0answers
34 views

NP-hardness of maximum set cover with element-level submodular function

Consider the following generalization of maximum set cover problem: Given a collection $C$ of subsets of a finite set $S$. Find $C^{'} \subseteq C$ of cardinality $k$ that maximizes \[ \sum\...
1
vote
1answer
231 views

Verifying if a greedy solution is optimal for a specific instance (Set cover)

Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution. Is there an efficient way of verifying if, for that particular instance, the given solution ...
2
votes
2answers
941 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
1
vote
1answer
117 views

Optimal covering of 2D matrix elements given spatial constraints

I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction. I've ...
2
votes
0answers
54 views

Given multiple families of sets, select a set from each such that the intersection of selected sets is a correspondence

Let $X = \{x_1, ... , x_k\}$ and $Y = \{y_1, ... , y_h\}$. A subset $S \subset X \times Y$ is a correspondence if : $\forall x, \exists y, (x,y) \in S$ and $\forall y, \exists x, (x,y) \in S$ That ...
15
votes
1answer
713 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 ...
1
vote
1answer
653 views

Set cover problem with sets of size 2

I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time? ...
3
votes
0answers
171 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
0answers
45 views

On the complexity of Unique Coverage Problem restricted to geometrical settings

I come to you with a problem I have been struggling with for the past few weeks. I would like to classify (complexity) a special case of Unique Coverage. To set the mood on, I will start by ...
1
vote
1answer
82 views

Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within ...
1
vote
1answer
98 views

Approximation rate for Greedy Set Cover algorithm (RESOLVED)

Set Cover: Consider a set of points X and Si a subset of X. The goal is to get the minimum number of subsets Si such as all points in X are covered. An example is shown by figure bellow. In this case, ...
2
votes
0answers
51 views

Smallest set non-disjoint with other given sets

Given a number of sets, what is the best algorithm to calculate the smallest set S such that S is not disjoint with any of the given sets?
0
votes
1answer
312 views

Reduce Clique to Set Cover

Is it possible directly to reduce clique to set cover? I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to ...
0
votes
0answers
82 views

Variation on weighted set cover, cover by consecutive pairs

Input: A set $N = \{1, \dots, n\}$, subsets/consecutive pairs $S_1 = \{1,2\}, \dots, S_n = \{n,1\}$ with associated costs $c_1, \dots, c_n \in \mathbb{N} \cup \{0\}$, and a subset $B \subseteq N$. ...
3
votes
1answer
254 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 ...
1
vote
2answers
3k views

Vertex cover algorithms for directed graphs?

I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph. Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a ...
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 ...
2
votes
1answer
284 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
313 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 ...
1
vote
1answer
71 views

Minimum covering problem formulation

Shouldn't I post this question on mathematics.stackexchange.com? Let be an airlaine company which has to affect its aircrew to several flights. We group som flights in subset, every flights of a ...
1
vote
1answer
63 views

Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S

Given a universal set of elements $\mathbf{U} = \{a_1, a_2, .., a_n\}$, a set $\mathbf{R} = \{a_i\} \subset \mathbf{U}$ where $i ϵ \{1, .., n\}$, a set $\mathbf{P} = \{R_1, .., R_m\}$ and a set $\...
4
votes
1answer
141 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 ...
1
vote
1answer
533 views

Is the exact cover problem NP-hard when there is a restriction on the size?

The exact cover problem with restrictions on the size is: Input: Given a set $U=\{1,2,\ldots,n\}$ and a collection of $C$ of subsets of $U$. Question: Is there a subcollection $C^\star$ of $C$ such ...
2
votes
1answer
60 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
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 = ...
1
vote
1answer
715 views

What is Unique Coverage Problem?

I am trying to understand the problem statement and the approximation algorithm for the Unique Coverage Problem from these notes. I have refined the question based on the comments provided. Thanks to ...
4
votes
1answer
177 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 \...
3
votes
1answer
224 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
1answer
186 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 $...
0
votes
1answer
474 views

Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows: Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{...
3
votes
2answers
727 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+...
2
votes
1answer
63 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 ...
1
vote
1answer
500 views

Problem with understanding the lower bound of OPT in Greedy Set Cover approximation algorithm

From what I know of analyzing and designing approximation algorithms, we need to find a lower bound on the optimum (in the case of minimization). For example if our solution is greedy ($SOL_G$) and if ...
1
vote
1answer
210 views

Another version of the online set cover problem?

Here is a note about online set cover problem: we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e_t$ and learn which sets ...
11
votes
1answer
329 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=\{...
2
votes
1answer
117 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 \...
1
vote
1answer
45 views

How can I convert a list with duplicates into a set for a reduction to the set cover problem?

I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here. Here's a condensed version of the problem: You're given a collection ...
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\}$ ...
6
votes
1answer
63 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 ...
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. ...
2
votes
1answer
81 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 ...
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 ...
1
vote
1answer
204 views

Proving NP hardness of maximum sum of means of a partition into k sets

I am trying to show the following problem is NP-hard and would like some help. Inputs: Integer $k$, and unordered set of $N$ numbers, $O$ Output: the $\max \sum\limits_{S_i \in S} \operatorname{mean}(...
2
votes
1answer
808 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?
5
votes
1answer
401 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 ...
2
votes
1answer
578 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 ...
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\...