Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
8 votes
0 answers
99 views

Problem of constructing binary sequence with least possible 1s under given constraint

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the ...
Relja Šegvić's user avatar
0 votes
0 answers
63 views

will it help to find the optimal solution to set cover problem if all exact-covers of the same problem were found

I have a set cover problem in the real world, it is a unicost set cover problem, with many subsets(around 10~30 million subsets, yes, no mistake here). Due to the nature of the problem in real world, ...
user166244's user avatar
1 vote
0 answers
38 views

Set cover variation: disjoint covers for all but one element

In the classical set cover problem, we are given the set $U$ of elements $\{1, \dots, n\}$ and a collection $C$ of some subsets such that their union is the whole set. Now, I will introduce the first ...
cgss's user avatar
  • 111
1 vote
1 answer
57 views

Choose edges in fully connected weighted graph that minimize sum of weights

I was looking at the Advent of Code 2023 day 11 problem and misread it to think that the question ended up asking something akin to what's below (after transforming the positions of the "galaxies&...
Orion Yeung's user avatar
0 votes
1 answer
24 views

Enumerating proper intersections

Let $U \subset \mathbb{N}$ be a finite universe set; $B$ be a set of nonempty subsets of $U$ such that $B$ covers all elements in $U$, i.e. $\bigcup_{b \in B} b = U$, and if $b \in B$ then $b \...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
44 views

Reduction from novel problem to Set Cover

i would like to perform a reduction for my novel problem to preferably the set cover problem, but i am a bit lost.. My problem can be described as follows: Suppose you have given an binary word as ...
Sven Fiergolla's user avatar
1 vote
1 answer
67 views

Maximum Weighted coverage approximation algorithm?

I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version. How should I modify the algorithm above to ...
calveeen's user avatar
  • 141
2 votes
0 answers
87 views

Data structure for prefix covering

I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that: each element belongs to a small number of subsets each prefix is a union of small number of subsets (these ...
ocksumoron's user avatar
0 votes
0 answers
39 views

How to prove Set-Cover problem is NP hard via reduction from Clique problem?

Since I know that the reduction Clique $\leq_{p}$ Vertex-Cover and Vertex-Cover $\leq_{p}$ Set-Cover are possible, I know how to show this using transitivity property of reductions. However is there ...
Yavuz Bozkurt's user avatar
2 votes
1 answer
63 views

Minimal set of elements needed to satisfy property counts

I have a friend who works in education. Sometimes, they need to create customized "word lists" to help students practice reading. These lists are limited in length, and must contain ...
Aderyn Thomas's user avatar
2 votes
1 answer
110 views

Algorithm to find intersection between collection of sets

I have two dataframes representing products two distributors sell. They look like this: df1 for distributor 1. ...
nepee's user avatar
  • 280
0 votes
1 answer
81 views

Minimal Hitting Sets Problem

Let $\mathcal{I} = \{I_0, \ldots, I_{m-1}\}$ a collection of subset of some universe $U$. We want to find a partition $P$ of $\mathcal{I}$ of minimal cardinality such that the intersection of each set ...
matteo_c's user avatar
  • 173
3 votes
0 answers
162 views

Maximum set cover with non-overlap

Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that: $s_i \in S$ $\forall ...
in_question's user avatar
0 votes
1 answer
121 views

Greedy Algorithm for Geometric Set Cover

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem. The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
Sandra's user avatar
  • 63
0 votes
1 answer
67 views

Geometric Set Cover in one dimension

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem. The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
Sandra's user avatar
  • 63
1 vote
1 answer
53 views

Modified set cover to identify "orthogonal" partitions

Setup I have a non-empty set of elements $U$ that are arranged spatially. I would like to partition $U$ into $N$ non-empty, disjoint subsets, $A_i$, having up to $M$ elements each. Each subset is only ...
user155171's user avatar
1 vote
1 answer
26 views

Efficiently covering a finite set of points in $\mathbb{Z}^3$ by fixed size, axis-aligned cubes?

In my problem of interest I have an arbitrary, finite set $S \subset \mathbb{Z}^3$. And I would like to cover $S$ with a set $C \subset \{T | T \subset \mathbb{Z}^3 \textrm{ is an axis-aligned cube of ...
EarlyGame's user avatar
2 votes
1 answer
207 views

Lower Bounding Set Cover's Approximation Ratio

I am reading Slavik's paper A Tight Analysis of Greedy Set Cover. Specifically, Slavik considers the unweighted version of set cover where the ground set is ${U = \{1,\ldots,m\}}$ for arbitrarily ...
ZaydH's user avatar
  • 121
2 votes
0 answers
45 views

Lowest total cardinality mutually exclusive construction of a superset

Let there be $N$ sequences containing at least one set each. Each set has at least one element each. Select exactly one set from each sequence. The selection within each sequence is mutually exclusive....
Reinderien's user avatar
2 votes
0 answers
159 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 ...
NayCey's user avatar
  • 111
1 vote
1 answer
205 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 ...
Chen Reddy Sundeep's user avatar
1 vote
1 answer
178 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 ...
NiRvanA's user avatar
  • 159
1 vote
0 answers
59 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 ...
NiRvanA's user avatar
  • 159
1 vote
0 answers
99 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 ...
Matt D's user avatar
  • 313
3 votes
0 answers
58 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 ...
Carson Baker's user avatar
1 vote
0 answers
129 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 ...
Zhang Yu's user avatar
1 vote
0 answers
135 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$; ...
Jack Zhou's user avatar
1 vote
0 answers
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 ...
mafu's user avatar
  • 339
1 vote
1 answer
134 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 ...
curiouscupcake's user avatar
2 votes
0 answers
135 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\}$...
Sugyani's user avatar
  • 21
2 votes
2 answers
114 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. ...
moyukh's user avatar
  • 23
1 vote
1 answer
72 views

Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
Radio Controlled's user avatar
6 votes
2 answers
225 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 $\...
Tassle's user avatar
  • 2,522
1 vote
0 answers
48 views

Complexity of solving fractional constrained set multicover

Recently, I've encountered the following problem: Given a collection of sets $S_1 \dots S_n$ of elements $e_1 \dots e_k$ with element $e_k$ denoted privileged, and a $k-1$-vector $r$, choose at most $...
Lesser Cormorant's user avatar
1 vote
1 answer
89 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 ...
Rohit Pandey's user avatar
2 votes
1 answer
2k views

Counterexample to greedy solution for set cover problem

I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows: 1-6. The set cover problem is as follows: given a set of subsets $S_1,\dots,...
mike's user avatar
  • 123
2 votes
2 answers
414 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 ...
Mark97's user avatar
  • 41
0 votes
0 answers
101 views

Minimum Dominating Set

Consider a graph $G$ with minimum degree $d$, we know through sets cover, it's possible to find the one dominating set $S$ that covers $G$ such that $$S\leq O(\log n)\frac{n}{d} $$ with high ...
Cain Porter's user avatar
1 vote
0 answers
350 views

Is this a hitting set or set cover problem? [closed]

Define a universe $U$ containing $N$ elements. We are given $N$ sets, each of which is a set. For example, $U = \{1, 2, 3, 4\}$ and sets \begin{align} S_1 &= \{\{1\}, \{2, 4\}\}, \\ S_2 &= \{\{...
da4kc0m3dy's user avatar
2 votes
1 answer
111 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 ...
Mostafa's user avatar
  • 159
1 vote
1 answer
53 views

Find the n best choices while maximizing value

Given: A list of slots (A, B, C, ...) Every slots supports a list of choices (C0, C1, C2, C3...) Every choice has a value All slots must be filled with at most n different choices. The sum of the ...
tomfroehle's user avatar
0 votes
1 answer
75 views

Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?

After removing multi-sets and sets that have elements that don't exist in $S$. $S$ = $[9,6,7,4,5,1,8]$ $C$ =$[[9,6,7],[4,5],[1,8]]$ Transform the values in $C$ of the shared index values with $S$. ...
Dingle Berry's user avatar
3 votes
1 answer
523 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 ...
Questionmark's user avatar
0 votes
1 answer
41 views

What practical/efficient algorithms exist for minimum weighted set cover problem (MIN-WSCP)?

For TSP there are well known heuristic and approximation solutions which run in low-polynomial time, like Christofides / 2-OPT and so on. I need a practical, fast algorithm, ideally sub-quadratic ...
Brendan Hill's user avatar
2 votes
1 answer
2k views

Is time complexity of the greedy set cover algorithm cubic?

I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements....
Max Herrmann's user avatar
1 vote
1 answer
86 views

Selection over combinatorics that satisfies a distribution

I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not. Here is the problem : Consider a list of M ...
Mehmet Doğan's user avatar
3 votes
1 answer
161 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 $\...
Robert Rovetti's user avatar
2 votes
0 answers
51 views

Boolean matrix / satisfiability problem [duplicate]

Let $M$ be an $m\times n$ matrix with all elements in $\{1,0\}$, $m >> n$. Let $\mathbf{v}_0, \ldots, \mathbf{v}_n$ be the columns of $M$. I want to find all sets of columns $S = \{\mathbf{v}_{...
Andrew's user avatar
  • 121
4 votes
1 answer
282 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$ ...
chyle's user avatar
  • 464
1 vote
1 answer
241 views

Tight analysis for the ration of $1-\frac{1}{e}$ in the unweighted maximum coverage problem

The unweighted maximum coverage problem is defined as follows: Instance: A set $E = \{e_1,...,e_n\}$ and $m$ subsets of $E$, $S = \{S_1,...,S_m\}$. Objective: find a subset $S' \subseteq S$ such ...
user112306's user avatar