# algorithm that removes extraneous connections from a graph

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
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)?

• Do you want to find all edges that can be removed? If so, I don't think that can be done in $O(|V|)$ time; solving this problem seems to require reading all vertices and edges, and it takes $\Theta(|V|+|E|)$ time even to read the input, let alone do any interesting computation on it, so it seems that any solution to this problem will need at least $\Omega(|V|+|E|)$ time.
– D.W.
Jun 11, 2017 at 4:48
• What does "destroy" mean? Keeping the graph connected? In that case, spanning trees are what you're looking for.
– Raphael
Jun 11, 2017 at 9:53
• Finding an arbitrary cycle in $O(|V|)$ seems quite doable. Jun 11, 2017 at 9:55
• I assume by "connection" you mean the same thing as "edge". I was already assuming you are given a list of all edges (connections). That's what it means for an algorithm to be given a graph $G$ as input: part of the specification of the graph is a list of all edges (at least, when the graph is specified in adjacency list representation, which is the standard assumption if no other information is provided). So that doesn't change my answer.
– D.W.
Jun 14, 2017 at 15:50
• Are you talking about the transitive reduction of a graph? Jul 14, 2017 at 17:50

You describe the graph as

• $V$ - a set of vertices
• $E$ - a set of edges, where each edge is (presumably) an unordered pair.

To determine where you can go from each vertex $v \in V$, you need to scan the whole of $E$, so you are already $\Theta (|V| + |E|)$.

If the graph is in the form ... $$V \rightarrow 2^V$$ ... then you can find a spanning tree in $\Theta(|V|)$. To enumerate the edges left out, you are up to $\Theta (|V| + |E|)$ again. But if you don't need to enumerate them, you can determine whether any given edge is spare in constant time.

Correction

If the graph is in the form $V \rightarrow 2^V$, then you can find a spanning tree in $\Theta(|V|)$.

I think this is wrong. Whatever your search order, at each vertex you have to look through the neighbours to find an undiscovered one, which might be the last. Depending on the structure of the graph, this might happen at every vertex. So the worst case at least is $\Theta (|V| + |E|)$.