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 $\mathcal{R}$ of subsets of $X$. We also have an undirected graph $G$ with vertex set $\mathcal{R}$ and edges representing incompatibilities between sets. The goal is to find a minimum set cover of $X$ which is also an independent set of $G$. Does this problem have a name? Or is it a special case of a studied problem? Or can it be reduced to a well-studied problem with a small blowup in runtime? (by "small blowup" I mean not simply polynomial, but preferably a small degree polynomial). I'm particularly interested in the geometric variant where $X$ is a set of points and the sets in $\mathcal{R}$ are defined as the intersection of $X$ with some simple geometric ranges (in which case tools such as VC-dimension, $\epsilon$-nets, range-searching and so on might come in handy for approximation algorithms). But I welcome any relevant reference.

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 maximizes the number of new elements at each turn (same as the one proposed in the Wikipedia article). However it is not as trivial to reach a result about the approximation ratio of this greedy approach. So I did some research and found these lecture notes that describe some useful concepts for this problem and also proves a lemma. Now let me iterate what is said in these lecture notes before we get to the lemma. Maximum Coverage problem Given a set of sets $U=\{S_{1},\dots,S_{m}\}$ and a number $k$, choose (at most) $k$ sets such that the union of the sets is maximized, or $\max_{I\subseteq U}\vert \cup_{j\in I}S_{j}\vert$ for some index set $I$. The sets may have elements in common. Let $\mathbf{OPT}$ denote the optimal solution, i.e. numbers at most covered by $k$ sets, let $a_{i}$ denote the number of newly covered elements in the $i$:th iteration by the greedy algorithm, let $b_{i}$ be the total number of covered elements in the $i$:th iteration, i.e. $b_{i}=\sum_{j=1}^{i}a_{i}$, and let $c_{i}$ be the number of uncovered elements at the $i$:th iteration, i.e. $c_{i}=\mathbf{OPT}-b_{i}$. Moreover, $a_{0}=0$, $b_{0}=0$ and $c_{0}=\mathbf{OPT}$. Lemma: The number of newly covered elements at the $(i+1)$:th iteration (i.e. $a_{i+1}$) is always greater than or equal to $(1/k)\cdot$number of uncovered elements at the $i$:th iteration, or $a_{i+1}\geq c_{i}/k$. Proof: Optimal solution covers $\mathbf{OPT}$ elements at $k$ iterations. That means, at each iteration there should be some sets in $U$ whose size is greater than or equal to the $(1/k)$ of the remaining uncovered elements, i.e., $c_{i}/k$. Otherwise, it was impossible to cover $\mathbf{OPT}$ many elements at $k$ steps by the optimal solution. Since the approximation algorithm is greedy, i.e., choosing always

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 $\bigcup S = X$. Consider the task of finding all inclusion-minimal covers of $X$. (Covers are inclusion-minimal if the removal of any subset $s_i$ from the cover destroys its coverage property.) Given the set of inclusion-minimal covers $C=\{c_1, c_2, ... c_m\}$, what is an upper bound for $\max|c_i|$, that is, the largest inclusion-minimal cover? It seems fairly straightforward to show that one upper bound is $|X|$ (that is, an inclusion-minimal cover will contain at most the same number of subsets as there are elements in $X$ itself). But can a better bound be found? Additional information: No restrictions are assumed for $S$. The bound would ideally be expressed in terms of one or more properties of $S$ (in whatever form those might take). A conjecture: If $\min |s_i| = k$, then $\max |c_i|$ (the size of the largest inclusion-minimal cover) is bounded above by $|X| - k + 1$. This is based upon two observations: (1) In constructing any inclusion-minimal cover, we start with any element from $S$ (call it $s_{1'}$). As $s_{1'}$ covers a particular subset of elements from $X$, the next added cover element (call it $s_{2'}$) must cover at least one new element from $X$ not covered by $s_{1'}$. (2) If $\min |s_i| = k$, then we can choose the first element $s_{1'}$ in our cover to have size $k$. This leaves $|X| - k$ elements in $X$ left uncovered. By the first observation, each additional $s_i$ must cover at least one new element in $X$, so we can add at most $|X| - k$ additional elements to the cover, leading to a cover size at most $|X| - k + 1$. As noted in the comments, this type of bound might not be significantly smaller than $|X|$ itself. However, I am hoping to use this in a combinatorial context, so any savings helps. Even smaller bounds

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$ lies in $S$}\}$$ My question is if the following (new problem) has a definite name in literature, and if not what should be the most appropriate name. New Problem: Given an $n$ vertex graph $G=(V,E)$ and an integer $k$ , find a set $S(\subseteq V)$ of size $k$ such that $|N[S]|$ is maximized. For the second problem, some of the names I have seen in the literature are maximum-graph-coverage; partial-coverage; k-dominating-set, (however, the exact same names are also used in other contexts).

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}$ such that $|\mathcal{H} \cap S_i| \geq 1$ for all $1 \leq i \leq n$. We may ask for the minimal cardinality of $\mathcal{H}$, that is, what is the least number of elements needed to "Hit" every $S_i$? Further, we may use a greedy algorithm to ensure we find a hitting set. In this greedy algorithm, we set $\mathcal{H} = \emptyset$, and while we still have sets $S_i$ that have not been hit, we add to $\mathcal{H}$ an element whom appears in the most $S_i$ that have not been hit, breaking ties arbitrarily if there are any. My question is: What is an example of a Universe set $\mathfrak{U}$ and subsets $S_i$, where $1 \leq i \leq n$ for some $n \in \mathbb{N}$, such that the greedy algorithm above does not find a minimal Hitting Set $\mathcal{H} \subset \mathfrak{U}$? For a longer (and probably clearer) description, and more info on the Hitting Set problem, see http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, or Prove that Hitting Set is NP-Complete.

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 is the minimal with respect to set inclusion and a hitting set consists of the vertices labeling the edges on the path from the root to the leaf. However, both grey and black colored hitting set consists of 3 vertices. Why grey colored leaf is not minimal in this case? Related question: Given a set of sets, find the smallest set(s) containing at least one element from each set

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 objective is to find some cover $C \subset \Lambda $ such that $\cup_{A\in C}A = S$ and $|C|$ is minimized. That is, find the minimum number of $A$'s needed to cover every element of $S$. The variation we will consider has two key alterations: - Rather than finding some cover $C$ such that $|C|$ is minimized, we want to cover as much of $S$ as possible, given some budget $k$. That is, let $F\subset S$ be the elements that are covered by $C$, our objective is to maximize $$\big|F \cap S\big|$$ such that $|C| \leq k$. - Rather than considering an element $s \in S$ covered when $s$ appears in at least one $A\in C$, we require that $s$ show up in 2 distinct $A$'s to be considered covered. (Any multiple is also interesting, even heterogeneous ones for each $s\in S$, but for now 2 is good enough). So far I can show that it is an NP optimization (reduction from set-cover), and that a $n-$approximation exists by simply looking any element $s$ that appears in some $A_i$ and $A_j$ and then selecting $C = \{A_i, A_j\}$, but this is a rather unsatisfying approximation. Is this variation NP-hard to approximate to a constant factor?

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 describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover. Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m n$?

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 $I$ there should be some time point $t$ from the chosen set such that $t \in I$. However, I am not sure if it's that straightforward. I tried modeling it as a minimum edge cover problem ("P" polynomial time complexity: intervals are vertices and intersection between intervals is an edge), but that doesn't work because for 1 time point in optimum solution there can be multiple edges. I developed a greedy solution: have intervals sorted in increasing order of their end times. Then iterate over the intervals in the order. If a time point hasn't been inserted into the solution that covers the current interval, then insert it and remove all intervals that are covered by it from consideration. Continue till no intervals remaining. Example: (0, 10), (3, 12), (11, 15) Add time 10 to the solution. Remove (0, 10) and (3, 12) from consideration. Add time 15 to solution. Remove (11, 15) from consideration. Final solution is of size 2. (time 10 and 15). I can't prove it's optimum because it's not modeled as edge cover or vertex cover or known graph problem. I tried modeling it as "minimum clique cover problem" but not sure if it works. - How to model it properly to understand its complexity (P vs NP complexity)? - How to know if the above solution is optimum?

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 time algorithm that computes: $$\mathbb{Pr}\left[ U =\bigcup_{X \in T} X \right]$$ Or is there any equivalent famous problem?