If you want to make money online : Register now

# [Solved]: Cycle of length k with no repeated edges

, ,
Problem Detail:

I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with no repeating edges, of a size at least k? (i.e. the number of edges in the cycle is at least k)

I thought that this problem can be reduced somehow to the euler cycle problem, but have no idea how to do this.

Thanks

#### Answered By : R B

This problem is NP-Complete.

The $\in NP$ part is simple - guess a trail and check it.

The hardness part comes from the fact Hamiltonicity on a cubic graph is hard, as proved in Garey and Johnson book.

(In a cubic graph, every vertex-simple path walk is edge-simple, as it can not visit a vertex more than once, except maybe the start and end vertex).

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35524

3.2K people like this