6

Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other. Given two numbers $a<b$ with $a\in S_i$ and $b\in S_j$ and $\lvert S_i\rvert\le\...


6

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem). We first sort the intervals by their right end point. Suppose the sorted order is $I_1, I_2, \ldots, I_n$. Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval ...


5

The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of ...


5

If no points in $C$ lie exactly on the mid-point of an edge in $\mathcal{G}$, then it suffices to associate each point in $C$ to the nearest vertex in $\mathcal{G}$. I will leave it as an exercise to the reader to prove this (hint: prove by contradiction). On the other hand, if points in $C$ are allowed to lie on the mid-point of edges, then we can provide ...


5

This is called the "Interval Scheduling" problem in the book [1]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above): sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$. while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}...


5

It was easier for me to show that the $k$-clique problem is a special case of this problem. On an input graph $G$ and an integer $k$, the this special case is defined by $G$,$k$,$t$, with $t=\binom{k}{2}=k(k-1)/2$. Observe that some $V'\subseteq V$ of size $k$ is a clique in $G$ if and only if the set $V'$ covers at least $\binom{k}{2}$ edges twice. ...


5

Set-cover heuristics are used in random testing ("fuzz testing") of programs. Suppose we have a million test cases, and we're going to test a program by picking a test case, randomly modifying ("mutating") it by flipping a few bits, and running the program on the modified test case to see if it crashes. We'd like to do this over and over again. If we do ...


5

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3]...


4

The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the 3-dimensional matching problem.


4

Hine: Given an instance of set cover, add $k-1$ copies of the set $\{1,\ldots,n\}$.


4

You have shown that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then the greedy algorithm finds $k$ sets which cover at least $n/2$ elements, and so at most $n/2$ elements are left uncovered. You can prove by induction that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then for each $t$, the ...


4

Thanks for the edit! This isn't vertex cover; it's something different. There are simple algorithms for this problem. Decompose the graph into a dag of strongly connected components. (The dag is sometimes called "the metagraph".) Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one ...


4

Not sure if this is a real-world problem – solving sudokus can be reduced to an exact cover problem (note that exact cover is related to set cover, but not the same). You can find similar explanations here. Some fast solvers directly use Knuth's dancing links to solve sudokus, which is usually much faster than naive backtracking. However, the fastest solvers ...


4

Thanks to j_random_hacker's hint, I've found a solution to reduce Vertex Cover to the Grid Problem: We make a $|E|$-by-$|V|$ grid of 3-by-3 blocks, i.e. a $3|E|$-by-$3|V|$ grid, with vertices ordered as columns $\{v_1,\dots,v_{N_1}\}$ and edges ordered as rows $\{e_1,\dots,e_{N_2}\}$. We'll construct rectangles on this grid (the drawing below will help a ...


3

Any linear program has a dual linear program, whose constraints are in one-to-one correspondence with the variables of the primal program. Under mild conditions, the optimal value of the dual program coincides with the optimal value of the primal program, and certain conditions known as complementary slackness are satisfied by any pair of optimal solutions. ...


3

One can rephrase your question as follows: Given a matrix $A$ and a vector $b$ over $GF(2)$, find a vector $x$ of weight $k$ such that $|Ax-b|$ is as small as possible. A very similar problem was shown to be NP-complete by Stadnicki on cstheory: Given a matrix $A$ and a vector $b$ over $GF(2)$, does there exist a vector $x$ of weight at most $k$ such ...


3

The result you quote, due to Feige, has actually recently been improved by Dinur and Steurer (based on earlier work of Moshkovitz), who showed that unless $P = NP$, there is no polynomial time $(1 - o(1))\ln n$-approximation algorithm for set cover. This result states that if all you care about is the worst case approximation ratio, then you cannot ...


3

Hardness Your problem might be called "maximum minimal set cover". In particular, your problem feels like it might be related to minimum maximal matching, which is NP-hard. If you wanted to try to prove NP-hardness, you might try to see if you can find a reduction from minimum maximal matching. Algorithms Your problem can be expressed as an instance of ...


3

If you are trying to prove $NP$-Hardness of that problem, you need a reduction from (not to). Anyway, I don't think this is $NP$-hard (unless $P = NP$, of course) Suppose the $S_i$ are sorted. Suppose you decide that element $x \in S_j$ will be minimum. Now in each other set, you can find the smallest element greater (or equal to) $x$ using binary search, ...


3

Yes, it is still NP-hard. In fact, it remains hard even if you replace $\log_2 n$ with the constant 3. This follows by reduction from 3-dimensional perfect matching. 3-dimensional perfect matching is the following problem: Input: disjoint sets $X,Y,Z$ such that $|X|=|Y|=|Z|$; a set $T \subseteq X \times Y \times Z$ Question: does there exist a perfect ...


3

As quicksort comments, you can convert any set cover instance to your special case by adding dummy elements. Take a large enough pool of dummy elements, and put all of it into a new set $S_1$. Then add subsets of $S_1$ to the other sets to satisfy your cardinality condition, taking care to leave some of them out. Every solution has to take $S_1$, and ...


3

The problem you're describing sounds more like a Dominating Set style problem to me (vertices covering vertices, Vertex Cover is vertices covering edges), but because you allow the dominating vertex to be at any distance from the dominated vertex, the problem becomes much easier. I believe the problem can in fact be solved in (near) linear time (in the ...


3

This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching. Then, for each unmatched vertex, add an arbitrary edge containing that vertex. In fact, if all you want to know is whether there's an edge cover of size at most $k$, you don't need to construct the cover: the size of a minimum edge cover is $M ...


3

There is no polynomial-time algorithm that computes an exact solution (i.e. the probability expressed as a ratio of two nonnegative integers $a/b$) to your problem unless $\textbf{P} = \textbf{NP}$. I will show that such an exact solution would provide a polynomial time algorithm for set-cover. Let $(U, S \subseteq \mathscr{P}(U), k)$ be an instance of set-...


3

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP). Your second problem is a special case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the ...


2

This is related to a well known problem with a conjecture due to Karpovsky and Moskalev [1] (I still believe is open) that at most V-1 paths are needed. It is tied to conjector of Erdos, Goodman, and Posa [2]. If you want the state of the art today, I suggest doing a thorough reverse-citation search on [1]. [1] Karpovsky, M. G., and E. A. Moskalev. "...


2

I think you are being confused by the way the question is phrased. The question asks for a sequence of instances $I_n$, consisting of triples $\langle X_n,F_n \rangle$, such that $|X_n| = n$ and GREEDY-SET-COVER$(X_n,F_n)$ could have $C^n$ many results, for some constant $C>1$. These results come from the fact that at step 4 there could be many sets that ...


2

Let's reduce multiway cuts problem, a variant of minimum $k$-cut, to your problem. In particular, consider the minimum 3-way cut problem, which is NP-hard for all edge weight equal to 1 (see The complexity of multiway cuts). A (minimum) 3-way cut problem is: given a graph $G = (V,E)$ and terminals $s_1,s_2,s_3\in V$, find a minimum set of edges $E'\...


2

The first step is to eliminate the known set $s$. The idea is to find all covers of $S \setminus s$ using at most $k-1$ sets, and then augment the solution by adding all subsets of $s$ to all sets in any given cover in all possible ways. Details omitted. For the new problem, it is enough to find all covers of $S$ of size exactly $k$ which don't use $S$ or $\...


2

Hint: An instance of densest $k$-subgraph can be viewed as an instance of your problem, in which sets are vertices and elements are edges. More generally, to prove that a problem P is NP-hard given that a (seemingly) related problem Q is NP-hard, you need to come up with a polytime reduction from Q to P. If Q is strongly related to P, such a reduction could ...


Only top voted, non community-wiki answers of a minimum length are eligible