Feedback Edge Set and Cycle of minimum size n/2 NP-Complete 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 NP-Complete 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 NP-Complete:

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 NP-Complete (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.

bump

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 NP-complete 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.

Quote:

---

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