Is there an edge we can delete without disconnecting the graph?

Question

Before I start, yes this is a homework. I would not have posted here if I haven't been trying as hard as I could to solve this one for the last 14 hours and got nowhere.

The problem is as follows: I want to check whether I can delete an edge from a connected undirected graph without disconnecting it or not in O(V) time, not just linear.

What I have reached so far:

A cycle edge can be removed without disconnecting the graph, so I simply check if the graph has a cycle. I have two methods that could be used, one is DFS and then checking if I have back edges; the other is by counting Vs and Es and checking if |E| = |V| - 1, if that's true then the graph is a tree and there's no node we can delete without disconnecting it.

Both of the previous approaches solve the problem, but both need O(|E|+|V|), and the book says there's a faster way(that's probably a greedy approach).

Can I get any hints, please?

EDIT: More specifically, this is my question; given a connected graph G=(V,E), can I remove some edge e in E and have the resulting graph still be connected?

Vitrine

Be a little more precise in the statement. Are you asking "given a connected graph G=(V,E), can I remove a particular edge e in E and have the resulting graph still be connected?" or "Given a graph as before, does tehre exist some edge e in E that for which the resulting graph is no longer connected?" – Riti

Question edited, sorry. I need to CHECK whether I can remove an edge from E and still have the graph connected. – Vitrine

The technical term is bridge – Averroism

Answer 1

Any recursive traversal of the graph, marking nodes as they're visited and short-circuiting to return true if you ever run into a node that is already marked will do the trick. This takes O(|V|) to traverse the entire graph if there is no edge that can be removed, and less time if it stops early to return true.

edit

Yes, a recusive traversal of the entire graph requires O(|V|+|E|) time, but we only traverse the entire graph if there are no cycles -- in which case |E| = |V|-1 and that only takes O(|V|) time. If there is a cycle, we'll find it after traversing at most |V| edges (and visiting at most |V|+1 nodes), which likewise takes O(|V|) time.

Also, obviously when traversing from a node (other than the first), you don't consider the edge you used to get to the node, as that would cause you to immediately see an already visited node.

Labialize

Just can you explain to me your reasoning here, sir? Running recursive explore procedure on a connected graph normally takes O(|E|+|V|) because I need O(V) to mark the nodes, and O(2|E|) merely to check the edges that connect the nodes. Recursive or not, this doesn't get close to O(|V|), so how does returning true when countering a visited node boils down to O(V)? Also, if I return true when countering a visited, I might actually return true while back-tracking from a sink, I might say I have a cycle while I still haven't really check if I do or not. – Vitrine

Wow!! This now makes perfect sense! Thanks a lot, sir! – Vitrine

Aha. I thought there'd be some trick involving |E|=|V|-1 but I'm brain dead after the holiday and didn't see it. – Riti

Same happened here haha, I did actually consider DFS and returning, but never thought how that would lead to O(|V|) hehe. Thanks to all who tried to answer =) – Vitrine

Note that your other solution of counting the nodes and edges can ALSO work in O(|V|) time IF you stop after counting |V| edges... – Labialize

Answer 2

You list all edges E and take an edge and mark one by one the two end vertices visited. If during traversing we find that the two vertices have been visited previously by some edges and we can remove that edge.

We have to take edges at most |V| time to see whether this condition satisfy.

Worst case may go like this, each time we take an edge it will visit atleast new vertex. Then there are |V| vertices and we have to take |V| edges for that particular edge to be found.

Best case may be the one with |V| / 2 + 1 e

Kazan

Answer 3

Have you heard of spanning trees? A connected graph with V-1 edges.

We can remove certain edges from a connected graph G (like the ones which are creating cycle) until we get a connected tree. Notice that question is not asking you to find a spanning tree.

Question is asking if you can remove one or more edges from graph without loosing connectivity. Simply count number of edges and break when count grows beyond V-1 because the graph has scope to remove more edges and become spanning tree. It can be done in O(V) times if the graph is given in adjacency list.

Antiperspirant

Answer 4

From what I'm reading, DFS without repetition is considered O(|V|), so if you take edge e, and let the two vertices it connects be u and v, if you run DFS from u, ignoring e, you can surmise that e is not a bridge if v is discovered, and given that DFS without repetition is O(|V|), then this would, I guess be considered O(|V|).

Echopraxia

No, a full DFS, even without repetition is still O(|V|+|E|) since you need to look at all the edges to make sure they don't go to nodes that you haven't yet visited. If you stop the traversal as soon as you find a loop, however, that only requires looking at at most |V| edges. – Labialize

I guess I should have clarified, it seemed a bit obvious that once you find v, you've proven that e is not a bridge and thus answered the problem, sometimes forget that you can't take anything for granted in proofs :D – Echopraxia