For a nondirection graph $G=(V,E)$, I need to write an algorithm that finds connections that can be removed without destroying the graph (ex: a connection from a child of a child back to the root of the graph). I have created an algorithm with a runtime of $O(|V|+|E|)$ (utilizing BFS):
smallerGraph(G,s): for all vertex u from V[G]do color[u]=WHITE p[u]=NIL n[u]=NIL end for for all vertex u from V[G]do if color[u]==WHITE then modifiedDFSVisit(G,u) end if end for return 0 modifiedDFSVisit(G,u): color[u]GRAY for all vertex v from Adj[u]do if color==BLACK and p[v]!=u and p[n[v]]!=v then removeLink(u,v) end if if color[v]==WHITE then p[v]=u n[u]=v modifiedDFSVisit(G,v) end if end for color[u]=BLACK
Additionally, I am also looking algorithm that can solve the same problem, however this time with a runtime of $O(|V|)$. If this is possible, if someone could point me in the right direction, I would appreciate it. If it isn't possible, why? Would the answer change if I was given a list of the connections (as well as the number of connections)?