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

    for all vertex u from V[G]do
    end for
    for all vertex u from V[G]do
      if color[u]==WHITE then
       end if
    end for
    return 0
    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
      end if
    end for

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

  • 3
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 11, 2017 at 4:48
  • 7
    $\begingroup$ What does "destroy" mean? Keeping the graph connected? In that case, spanning trees are what you're looking for. $\endgroup$
    – Raphael
    Commented Jun 11, 2017 at 9:53
  • $\begingroup$ Finding an arbitrary cycle in $O(|V|)$ seems quite doable. $\endgroup$ Commented Jun 11, 2017 at 9:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Jun 14, 2017 at 15:50
  • 1
    $\begingroup$ Are you talking about the transitive reduction of a graph? $\endgroup$
    – Pål GD
    Commented Jul 14, 2017 at 17:50

1 Answer 1


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.


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|)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.