If you want to make money online : Register now

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

, , No Comments
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

Asked By : user2443613

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

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback