CODEWITHSUNDEEP
algorithmgraphcorrectness
user314159
user314159

Reputation: 13

Check if a simple, undirected graph is triconnected

Problem

Given a simple, undirected graph G = (V, E), where |V| = n = number of nodes and |E| = m = number of edges, check whether G is triconnected. That is, whether G remains connected (a path exists from each node to all the other nodes) after randomly removing any two edges. Required time complexity: O(n^2(n + m))

My solution

For each node in G do the following:

  1. Check whether the node has at least 3 edges to 3 different nodes: O(1).

  2. Ignore the node and run depth-first search on the remaining graph to check whether it is still connected: O(n + m)

Time complexity: O(n(n + m)) = O(n^2(n + m)).

Is my solution correct?

Upvotes: 1

Views: 352

Answers (2)

Sorin
Sorin

Reputation: 11968

You usually check connectivity with max flow. You set capactity 1 to every edge, pick two nodes and compute maxflow between them. The result is the number of completely different paths between the two nodes (different as in no shared edges). To make sure the entire graph is 3 connected means you need to pick every pair of nodes and compute max flow between them.

Max flow with Ford–Fulkerson algorithm has a complexity of O(m * max(f)) where max(f) is the max flow. However, since the algorithm looks to increase flow at every step we can stop as soon as flow == 3 (we don't care if there are even more paths). So this makes the complexity O(m).

Since you do this for every pair of nodes you get a complexity of O(n^2 * m). Since V <= E (especially after you do your quick edge count check) O(n+m) = O(m) so it's the same complexity as what's required.

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65506

No, consider the graph with vertices X and *.

  *   *
 /|\ /|\
*-+-X-+-*
 \|/ \|/
  *   *

This graph is 3-edge-connected but if you delete X, it's disconnected.

Upvotes: 2

Related Questions