2
$\begingroup$

I have a question regarding a graph algorithm which is as follows:

Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\{1, 2,\dots ,n\}$ we want to determine the smallest integer $k$ such that deleting vertices $1$ through $k$ results in a graph whose largest connected component has at most $n/2$ vertices (when we delete a vertex we also delete all edges incident to that vertex). Give an $O(m \log^* n)$ algorithm that determines $k$.

The graph at the beginning could be disconnected, nor at the end need it be connected. Since $O(m \log^*n)$ is almost linear, $\log^*n$ grows very very slowly like in union-find data structure so this algorithm is almost linear time like union-find. I am trying to solve it through union find but it seems I am doing something wrong. Now I think that I should use union-find as a black box, but I ca'nt figure it out.

This is a practice problem, not homework.

$\endgroup$
2
$\begingroup$

Hint: Try working backwards, adding vertices to the graph in reverse order $n,\dots,1$.

$\endgroup$
  • $\begingroup$ Can u please clarify this, because if i add vertices it would be the opposite of the problem. $\endgroup$ – user1325120 Feb 19 '14 at 23:07
  • $\begingroup$ As far as I understand if we start from a disconnected graph, and adding vertices using union find until we have a component of n/2 size?? $\endgroup$ – user1325120 Feb 19 '14 at 23:08
  • 1
    $\begingroup$ I'm only giving a hint since it's your exercise rather than mine. The best way to see if you understood the hint correctly is to solve the exercise. $\endgroup$ – Yuval Filmus Feb 19 '14 at 23:22

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.