# Tag Info

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

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

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)$...
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 ...

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