
February 16th, 2009, 03:22 PM
#1
Feedback Edge Set and Cycle of minimum size n/2 NPComplete Problems
I'm having some issues with a recently assigned homework and I'm just looking for some feedback to ensure that I am or am not retarded. I'm not looking for anyone to give detailed answers for the problems, I'm looking for someone to confirm or deny that these two problems are in fact NPComplete because I think there are polynomial solutions for both of them. The problems are the following:

Prove that the following or their decision versions are NPComplete:
Given an undirected graph of size n, find if there is a cycle of at least size n/2.
Feedback Edge Set (find the minimum set of edges in a directed graph whose removal will make the graph acyclic)

So, starting with the first one, the decision version is simply, find if there is a cycle of minimum size k in graph G. However, can't you simply do a depth first search from any vertex (assuming that the graph is connected, if it is not you have to run this from every vertex that hasn't been visited yet), record the depth that you are at as you go, and any time you encounter a back edge, that implies a cycle whose size can be determined by the depth of the node you are at, and the depth of the node the back edge goes to? Unless I'm crazy, that's a polynomial time solution.
Next, the feedback edge set problem. Now, to preface this problem I have already proved that Feedback Vertex Set is NPComplete (the same problem except that you are removing vertices instead of edges). That is done via a reduction from the Vertex Cover problem. However, the feedback edge set problem seems to have a polynomial time solution. Can't we just find a MST of the graph and edges not represented there must be removed in order for it to be acyclic? This won't be a minimum feedback edge set, but there's probably an easy way to move from that set to the minimum set.
Thanks for anyones help in advance.

February 18th, 2009, 12:12 AM
#2
Re: Feedback Edge Set and Cycle of minimum size n/2 NPComplete Problems

February 18th, 2009, 02:36 AM
#3
Re: Feedback Edge Set and Cycle of minimum size n/2 NPComplete Problems
First problem:
The number of possible cycles is exponential in the size of the graph.
Running a DFS starting from each vertex will not necessarily give you the lengths of all cycles in the graph  the length (or depth of the DFS search) is very much dependent on the order of visited nodes. It is indeed an NPcomplete problem.
As for the second problem 
1. Any spanning tree is the same as a MST since the graph is not weighted  you don't have one spanning tree you can consider better than another for this purpose.
This won't be a minimum feedback edge set, but there's probably an easy way to move from that set to the minimum set.
2. Again, since the number of possible cycles is exponential in the size of the graph, there is no known easy way to do it, sorry . If you will find an easy(polynomial) way then you will prove that P = NP  which is assumed to be false.
Regards,
Zachm
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
