Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edgedisjoint cycles of length $k$ in $G$? If not is there a proof that this problem is NPhard? I'm interested in approximation algorithms also.
Determining whether the edge set of a graph can be partitioned into copies of a fixed graph $F$ is NPhard once $F$ has a connected component with at least three edges. In particular, it's NPhard 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 edgedisjoint $k$cycles by removing them greedily.

$\begingroup$ If a graph is an edgedisjoint 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$ – Ben Barber Apr 8 '15 at 14:32