1
$\begingroup$

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

$\endgroup$
  • 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. Jun 11 '17 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 Jun 11 '17 at 9:53
  • $\begingroup$ Finding an arbitrary cycle in $O(|V|)$ seems quite doable. $\endgroup$ – John Dvorak Jun 11 '17 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. Jun 14 '17 at 15:50
  • 1
    $\begingroup$ Are you talking about the transitive reduction of a graph? $\endgroup$ – Pål GD Jul 14 '17 at 17:50
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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