# Tag Info

## Hot answers tagged covering-problems

### 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 ...
• 133
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 ...
• 4,986

• 328
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
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

### 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-...
• 151

### 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 ...
• 50.3k

### 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
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

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}... • 23.8k 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 - ... • 9,566 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