# Fastest algorithm for connectivity problem

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.

• 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? – Pål GD Jun 17 at 10:25
• @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. – user121300 Jun 17 at 10:38
• k+1 largest components, yes. – Pål GD Jun 17 at 11:02
• Can you credit the source where you encountered this task? – 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.

• 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. – D.W. Jun 18 at 7:13
• 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$. – Pål GD Jun 18 at 7:23
• Oh, right! Thank you for the explanation. – D.W. Jun 18 at 7:47