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,066
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 ...
- 133
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{...
- 2,143
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,642
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\...
- 723
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,642
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 ...
- 617
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-...
- 151
2
votes
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}...
- 24.3k
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 ...
- 50.9k
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,772
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,596
Only top scored, non community-wiki answers of a minimum length are eligible