# 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.

114 questions
Filter by
Sorted by
Tagged with
57 views

### Exact Cover variant: partition a family of subsets into exact coverings

I have found that a problem that I'm analyzing is equivalent to the following variant of the Exact Cover problem: Partition into $k$ Exact Covers Input: A universe ...
1 vote
56 views

### Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?

I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2. Set cover problem with sets of size 2 The ...
1 vote
32 views

### Trivial vertex cover in regular graph is 2-approximation Proof

I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover. My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
1 vote
36 views

### Prove that a dominating set has minimum cardinality in a "unit interval graph"

I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
1 vote
46 views

### Solution methods for this Weighted Partial Set Cover-ish problem

Given a set of subsets $S_1, ..., S_N$ of a finite universe $E$ of elements $e_1, ..., e_n$ and mapping of those elements to an integer 'weight' $w_1, ... w_n$, select the subset of subsets which ...
57 views

### What is the name for this minimal satisfying set covering problem? [duplicate]

Preface Hello! I have a problem here that's difficult for me to Google, and I don't know if there's a name for it. It feels like a set cover problem of some kind, but I'm very unfamiliar with ...
16 views

### How to "sort" stops when combining multiple bus routes (joint timetable)?

In a public transport system, it can happen that trips with partially different routes are written on one timetable. For example, if TRIP 1 has stops A-B-C-D and TRIP 3 has stops A-B-C-E, then the ...
1 vote
78 views

### A Special Case of Set Cover Problem: Covering Nodes of Tree using Paths [closed]

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s$ is a ...
1 vote
58 views

### Variant of "Exact Cover by 3-Set "

Exact cover by 3-sets is 𝖭𝖯-complete: Instance: Given a finite set $X = \{x_1, x_2, …, x_{3n}\}$ of $3n$ elements and a collection $C = \{(x_{i_1}, x_{i_2}, x_{i_3})\}$ of 3-elements subsets of $X$; ...
1 vote
19 views

### Find optimal starting point of recursive search, with solution known

An Exact Cover problem is commonly denoted as a matrix of 0s and 1s. Columns denote requirements, rows denote possible choices. The problem is solved when a set of rows was found such that, using just ...
1 vote
29 views

### Trouble to understand the proof of greedy algorithm for set cover

Problem definition: Given a universe $U$ of $n$ elements, a collection of subsets of $U$, $S = \{S_1,..., S_k\}$, and a cost function $c: S \to Q^{+}$. Find a minimum cost subcollection of $S$ that ...
58 views

### Upper bound on Set Cover Size

I am working on a related Steiner tree problem that I have reduced to Minimum Set Cover, but stumbled across this related problem and got stuck. Given an universe of $n$ elements $U = \{1,2,\ldots,n\}$...
75 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. ...
1 vote
31 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
144 views

1 vote
74 views

### Triangles covering all vertices of a tri-partite graph

This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers. I'm designing fictional fruits. Each fruit has three attributes; color, taste ...
636 views

47 views

46 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 ...
73 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 ...
262 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 ...
1 vote
178 views

### Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
175 views

### Minimal edge cover of the hypergraph

We know that minimal edge cover for the normal graph is polynomial time solvable. Is it also true for hypergraph?
179 views

### set cover to edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
1 vote
756 views

### set cover where only certain special subsets are allowed

I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate ...