1
$\begingroup$

Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges. Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific order. Suppose that we remove the edges from $G$ one at a time, in this order. Initially, the graph is connected, and at the end of this process the graph is disconnected. Therefore, there is an edge $e_i$ such that just before removing $e_i$ the graph has at least one connected component with more than $n/4$ nodes, but after removing $e_i$ every connected component of the graph has at most $n/4$ nodes.

Give an efficient algorithm that determines this edge $e_i$. Assume that $G$ is given to the algorithm as a plain linked list of the edges appearing in the order $e_1, e_2, \dots, e_m$. The worst-case running time of this algorithm must be asymptotically better than $O(mn)$.

Improve this question
$\endgroup$
4
  • $\begingroup$ Welcome to Computer Science! Your question looks like interesting. Please add a url or reference to the original source in the question. Besides avoiding possible plagiarism, that information motivates and helps more people answer your question faster and better. $\endgroup$
    – John L.
    Nov 17, 2018 at 5:20
  • $\begingroup$ Have you tried binary search? $\endgroup$
    – Yuval Filmus
    Nov 17, 2018 at 5:52
  • $\begingroup$ Please don't edit your question in a way that invalidates existing answers. $\endgroup$
    – Gilles 'SO- stop being evil'
    Nov 21, 2018 at 15:58
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    Nov 21, 2018 at 18:46

1 Answer 1

Reset to default
5
$\begingroup$

One naive thought would be that we can maintain the list of the size of current connected component. After removing an edge the content of the list will be changed and when the max member of this list decreased to no more than $n/4$ we can terminate and output the edge. However, simulating such process seems inefficient.

Though removing edge is somehow hard for us to maintain the size of connected component, adding edge is not.

We can consider the problem reversely:

Initially, there is no edge in graph $G$, then we add edge in the order of $e_n,e_{n-1},\cdots,e_1$ and at the end of this process $G$ is connected. Therefore there an edge $e_i$ such that just before adding $e_i$, every connected component of the graph has at most $n/4$ nodes, but after adding $e_i$, the graph has at least one connected component with more than $n/4$ nodes.

Obviously, such $e_i$ is just the edge we want for the origin problem.

We can use Union-Find Algorithm to maintain the size of each connected component. When adding an edge$(u,v)$, first check whether $u,v$ are in different connected components. If yes, then we get a bigger connected component and the size of it will be the sum of size of those two components, otherwise we do not need to do anything.

Once we find adding $e_i$ results in a connected component bigger than $n/4$, we can terminate and output it.

The overall time complexity is $ O(m\alpha (n)) $

Improve this answer
$\endgroup$
2
  • $\begingroup$ Pure genius. Runtime: I think there are n steps of taking an edge and checking if both vertices are in the same connected set, and at most n-1 operations of combining two connected sets into one since we start with n connected sets of size 1. So trivially done in O (m + n^2), but should be possible to do better. $\endgroup$
    – gnasher729
    Nov 17, 2018 at 20:02
  • $\begingroup$ @KevinDumaresq Reverse a linked list takes O(m) is right(However you can just write a for loop from n down to 1 instead if the edges are stored in an array). And for the Disjoint-set forests, the complexity for checking whether two nodes in same set(components) is O(alpha(n)), merging two sets is O(1), you may need to check m times therefore the overall worst complexity shall be O(m alpha(n)) $\endgroup$
    – Tsumiki Mikan
    Nov 19, 2018 at 8:20

Your Answer

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