Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this problem is NP-hard? I'm interested in approximation algorithms also.
1 Answer
$\begingroup$
$\endgroup$
1
Determining whether the edge set of a graph can be partitioned into copies of a fixed graph $F$ is NP-hard once $F$ has a connected component with at least three edges. In particular, it's NP-hard to determine the maximum number of $k$-cycles that can be packed into a graph.
If $k$ is even then the Turán number of $C_k$ is $O(n^{1+2/k})$, so for dense graphs almost every edge can be covered by edge-disjoint $k$-cycles by removing them greedily.
-
$\begingroup$ If a graph is an edge-disjoint union of $p$ $k$-cycles then obviously the optimum is $p$. Are you asking about the case when the $p$ $k$-cycles overlap? Or possibly whether it's easy to find a decomposition if you know that there is one? In either case, I'm afraid I don't know. $\endgroup$ Apr 8, 2015 at 14:32