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.