Let $G = (V,E)$ be any undirected graph. Let $k$ be some number and $C = |u \longrightarrow v|$ where $u \longrightarrow v$ means there is a path from $u$ to $v$. We want to add $k \subseteq V \times V\ E$ edges into $G$ such that $C$ is maximised in the new graph.

Question : What is the fastest algorithm for this problem?

I can solve the above problem in $n^{O(k)}$ time by brute force method.

  • $\begingroup$ Suppose that you can only add one edge, k = 1. What do you do? You add it arbitrarily between the two largest components, no? Suppose that you have two edges, k = 2? Connect the three largest components? $\endgroup$ – Pål GD Jun 17 at 10:25
  • $\begingroup$ @Pål GD I think you are suggesting an algorithm like this: first run DFS algorithm to find connected component and then choose first largest $k$ connected components and we are don. $\endgroup$ – user121300 Jun 17 at 10:38
  • $\begingroup$ k+1 largest components, yes. $\endgroup$ – Pål GD Jun 17 at 11:02
  • $\begingroup$ Can you credit the source where you encountered this task? $\endgroup$ – D.W. Jun 18 at 7:13

If I understand you correctly, you want to maximize the number of pairs of vertices that are connected.

In a connected (undirected) graph, all vertices are reachable from each other, so the number is always $n^2$.

You can always connect to components with an edge by placing it arbitrarily between the components, and this will increase the number from $a^2 + b^2 \leq (a+b)^2$ to $(a+b)^2$.

If $a \geq b \geq c$, then

$$(a + b)^2 - a^2 - b^2 \geq \max((b+c)^2 - b^2 - c^2 , (a+c)^2 - a^2 - c^2).$$

It follows that the optimal solution is to iteratively connect the two largest components in your graph, which corresponds to, given $k$ edges, connecting the $k+1$ largest components of your graph.

Finding the $k+1$ largest components can be done in $O(n+m)$ time.

| cite | improve this answer | |
  • $\begingroup$ Where does $a^2$ come from? Are you assuming that every component with $a$ vertices contains $a^2$ paths? The question asks about paths, not edges. $\endgroup$ – D.W. Jun 18 at 7:13
  • $\begingroup$ Yes, it was not completely precise, but the idea is that in a connected graph, $C$ (the number of pairs that are "connected") is $n^2 - n$. $\endgroup$ – Pål GD Jun 18 at 7:23
  • $\begingroup$ Oh, right! Thank you for the explanation. $\endgroup$ – D.W. Jun 18 at 7:47

Your Answer

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