9 votes

Covering string by palindromes

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example: A subquadratic algorithm for minimum palindrome factorization by Fici ...
9 votes
Accepted

Complexity of the edge-disjoint cycle covers

The problem is polynomial-time solvable. Say that a vertex is balanced if its in-degree equals its out-degree. Note that a directed graph is Eulerian iff every vertex is balanced and its underlying ...
5 votes

Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

Here is the proof of Petrank's reduction. This was suggested to me by Édouard Bonnet. I still do not know whether this can be turned into an L-reduction. Suppose there is a PTAS algorithm $\mathscr{...
4 votes
Accepted

Is there an approximation algorithm for MAX k DOUBLE SET COVER?

(Comment $\rightarrow$ Answer) Consider the following algorithms for a hypergraph $(U,\mathcal S)$, with $n=|U|$: For a set $X\subseteq \mathcal S$ of sets and a set $A \in X$, define $d_X(A)$ as ...
  • 1,633
4 votes
Accepted

Minimal clique edge cover vs minimalist (assignment-minimum) ones

Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\...
  • 328
3 votes
Accepted

Minimum number of triangles required to cover a complete graph?

Let $N(n)$ be the number of triangles needed to cover $K_n$. Because every triangle covers only three of the $n\choose 2$ edges, we have $\frac{1}{3}{n\choose 2}\leq N(n)$ as a lower bound. Note that ...
  • 597
3 votes
Accepted

Does the following type of hitting problem have a name?

I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem (introduced in this paper by Kortsarz). Roughly, an input to Min-Rep consists of a bipartite graph $G=(A;B,E)$...
  • 1,633
3 votes

Covering a binary relation as a union of rectangles

...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions. Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-...
2 votes

Geometric max cover

The problem of covering $n$ points in the Euclidean plane by $k$ unit balls is a special case of your problem that is already known to be NP-complete. It is also hard to approximate the optimal ...
2 votes

A generalization of edge cover

This problem is known to be NP-complete (since the 1970s). Dyer and Frieze established its NP-hardness even for the highly restricted special case where the graph $G$ is planar and bipartite: ...
  • 5,732
2 votes
Accepted

Long distance string problem

Look up the concept of anticodes. Some bounds exist. Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by ...
  • 2,016
1 vote

Minimum number of triangles required to cover a complete graph?

If $n$ is congruent to $1$ or $3$ modulo $6$, there is a covering of the complete graph $K_n$ with triangles so that each edge is used exactly in exactly one triangle, so this uses exactly $\frac{1}{3}...
1 vote

Geometric max cover

For the case of disks in the plane, there is a recent PTAS: https://arxiv.org/abs/1607.06665 There is also a fixed parameter tractable algorithm for this problem for spaces with bounded VC dimension - ...
1 vote
Accepted

Covering by disjoint sets

Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph $G=(V,E)$, define your ground set as $U:=V$ and for every vertex $v\in V$ construct a ...
  • 5,732

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