0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – Ben Barber
    Apr 8, 2015 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.