Connect a graph

Question

Given an undirected graph, We need to convert it into a connected graph by adding/removing the edges keeping the summation of absolute difference of change in degree of nodes minimum. There can be multiple edges. Formally, we need to minimize: $$\sum_{i = 1}^{i = n} |d_i - e_i|$$ Where, $e_i$ is the new degree of node i.

My approach was separating all the connected components first and then for every connected component, I noted down the edges which were not present in the DFS tree. These edges do not contribute to the connectivity of the graph and hence I can redirect them to other components to connect them. Is this claim correct? Also since the number of these type of edges can be arbitrary, what would be the constraints under which I use them to connect to other components.

The algorithm should work in linear time.

Answer 1

I'll just discuss the core idea of the algorithm and skip the details. It is easier to think that the connected components of your graphs are not singletons (If there are singletons, ignore their connected components. I will point out how to handle them in brackets).

You can modify your graph in a way that doesn't change the degree of any vertex and such that resulting graph will be either:

• Connected, or
• A forest

If neither of the above two condition is met then you can iteratively perform the following "merge" operation:

• Pick an edge $(u,v)$ from a connected component $C$ such that $C-e$ is still connected. This edge exists otherwise the graph would be a forest.
• Pick an edge $(x,y)$ from a connected component $C'$ other than $C$. $C'$ exists otherwise the graph would be connected.
• Replace $(u,v)$ and $(x,y)$ with $(u,x)$ and $(v,y)$. You have now a graph with the same degrees and one less connected component (effectively, $C'$ is now merged into $C$).

If the resulting graph is connected you are done (If the graph had singletons then reroute some of the edges not needed for connectivity to them, each of these rerouted edges contributes $1$ to the measure to minimize. If there are not enough edges then you'll need to add new ones, which contribute $2$ each to the measure).

If the resulting graph is a forest $F$ of $k>1$ trees then you'll need to add $k-1$ edges to connect the trees of $F$ (if there were singletons then consider them as trees in $F$).

You can implement this algorithm in linear time by keeping, for each connected component $C$:

• A list $T_C$ of the edges in a spanning tree of $C$,
• A a list $L_C$ of edges that are in $C$ but not in $T_C$.

Constructing these lists takes time $O(n+m)$ where $n$ and $m$ are the number of vertices and edges of the input graph, respectively. Then the edges $(u,v)$ and $(x,y)$ can be found in constant time. Pick $(u,v)$ from $L_C$ and $(x,y)$ from $T_{C'}$. In this way $T_C$ and $L_C$ can be updated in constant time to reflect the result of the "merge" operation. The number of "merge" operations is at most $O(n)$.