CODEWITHSUNDEEP
algorithmgraphgreedy
Fingolfin
Fingolfin

Reputation: 5533

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

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?

Upvotes: 7

Views: 8935

Answers (4)

user4279052
user4279052

Reputation: 1

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.

Upvotes: 0

YashM
YashM

Reputation: 121

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

Upvotes: 1

Chris Dodd
Chris Dodd

Reputation: 126418

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.

Upvotes: 9

PlexQ
PlexQ

Reputation: 3120

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

Upvotes: -1

Related Questions