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.

107 questions
Filter by
Sorted by
Tagged with
68 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 ...
41 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$; ...
162 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 ...
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 ...
1k 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....
24 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 ...
50 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\}$...
135 views

68 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 ...
358 views

183 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$ ...
46 views

45 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 ...
153 views

Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria

Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$, find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in ...
70 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 ...
211 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 ...
160 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 ...
151 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?
719 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 ...
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 ...