Minimally extend a tree such that there are no bridges in the new graph

Question

We are given an undirected tree on which we should add the minimum number of edges such that there are no bridges in the new graph.

An edge $e$ is a bridge if the graph with that edge removed is no longer connected.

For example, here is a tree with 8 nodes

1 2
2 3
3 4
4 5
3 6
3 7
3 8
At least three edges should be added. For example: (1, 6), (5, 7), (8,4)

In very small graphs we can brute force all possible new edges. However, this is too slow for bigger trees. I tried making some observations but I couldn't find anything that could solve the problem.

This problem is the task "NET" from Baltic Olympiad in Informatics 2015.

Answer 1

Start by proving the following statement:

Let $G=(V,E)$ be an undirected graph. There are no $\mathrm{bridges}$ if and only if there are two edge disjoint spanning trees of $G$.

Proof:

1. Suppose there are two edge disjoint spanning trees, $T_1, T_2$ of $G$.

   Now we remove an arbitrary edge. If it belongs to neither $T_1$, or $T_2$, we're done. If it belongs to $T_1$, it is therefore not in $T_2 $ (symmetrical for $T_2$) $\Rightarrow$ $G$ is still connected $\Rightarrow$ there are no $\mathrm{bridges}$ in $G$.

2. Suppose there are no two edge disjoint spanning trees. Then there is at least one cut $C^*$ of $G$ s.t $C^*=\{A, \bar{A}\}$ and $\delta(C^*) \leq 1$. Otherwise it is easy to constructively show there are two spanning trees.

   Let $e$ denote the edge between $A$ and $\bar{A}$. Since $e$ is the only edge connecting the two subsets, by removing it, $G$ is separated into two unconnected componenets, therefore $e$ is a $\mathrm{bridge}$

---

If you can add any edge you want, simply extend $G$ s.t there are two edge disjoint spanning trees. If you start from a tree, it means you have exactly $n-1$ edges, and to create another distinct spanning tree you would have at least $n-1$ additional edges.

If you can't add any edge you want, see http://i.stanford.edu/pub/cstr/reports/cs/tr/74/455/CS-TR-74-455.pdf by Tarjan on disjoint spanning trees (with algorithm)

Answer 2

If a tree $T$ becomes bridgeless after edges in a set $S$ have been added to $T$, we will say $S$ doubly connects $T$.

The minimum size of $S$ that doubly connects $T$ is $\lceil n/2\rceil$, where $n$ is the number of the leaves in $T$.

The simple idea is that the edges to be added should only connect leaves of the tree. After we have selected an edge to be added, we can delete its two vertices and some related vertices and edges so that the remaining tree has two less leaves. We will make sure that solving the problem for the remaining tree is enough to solve the original problem.

Outline of an algorithm

Input: A tree $T$ whose vertices are $0, \cdots, n-1$ where $n\ge2$. The set of vertices that are neighbours to vertex $v$ is $N[v]$.

Output: A list of edges whose size is minimum such that $T$ with those edges added is bridgeless.

Helper procedure to delete a vertex $v$ of degree 2: Suppose $x$ and $y$ are the two vertices connected to $v$. Mark $v$ as deleted. Replace $v$ in $N[x]$ with $y$. Replace $v$ in $N[y]$ with $x$. Note that $T$ remains a tree after the procedure.

Helper procedure to delete a leaf: Suppose $v$ is a leaf that is connected to $u$. If $u$ is a leaf, just return. Otherwise, do the following. Mark $v$ as deleted. Delete $v$ from $N[u]$. If the degree of $u$ is 2, apply the procedure above to delete $u$.

Main Procedure:

1. Delete all vertices of degree 2.

   Now each vertex is either a leaf or connected to two or more other vertices.

2. Let $S$ be an empty list. Loop the following.

   1. Find a pair of leaves the distance between which is at least 3. Let them be $u$ and $v$. Add edge $(u,v)$ to $S$. Apply the helper procedure to delete $u$ and $v$.
   2. If no such pair can be found, break the loop.

3. Now $T$ has no path of length 3 and each vertex of $T$ is either a leaf or connected to two or more other vertices. There are two cases.

   • $T$ has only one edge. Let it be $(u,v)$. Add edge $(u,v)$ to $S$. (If we add the edge $(u,v)$ in $S$ to the tree, we will have two edges connecting $u$ and $v$. This is the only place where we introduce a parallel edge.)
   • $T$ has three or more edges. $T$ must be a star graph. Let the center vertex be $u$ and other vertices be $v_1, \cdots, v_m$. If $m$ is even, add edges $(v_1, v_2)$, $(v_3, v_4)$, $\cdots$, $(v_{m-1}, v_{m})$ to $S$. If $m$ is odd, add edges $(v_1, v_2)$, $(v_3, v_4)$, $\cdots$, $(v_{m-2}, v_{m-1})$ as well as edge $(v_1, v_m)$ to $S$.

Implementation of the algorithm

There are a few ways to implement step 2.1.

A naive way to find a pair of such leaves is to do a depth first search from any vertex.

In order to find such pair of vertices faster, we can also select any two neighboring internal node $x$ and $y$. The edge $(x,y)$ splits $T$ into two subtress, one part that has $x$ and the other part that has $y$. We can pair any leaf of $T$ in one part with any leaf of $T$ in the other part. We can do this recursively.

Exercises

Exercise 1. If an edge set $S$ doubly connects a tree $T$, then then $|S|\ge\lceil n/2\rceil$. (Hint, each leaf of $T$ must be an endpoint of some edge in $S$.)

Exercise 2. Use the notations in the algorithm. Show the algorithm is correct by verifying the following.

1. For an iteration in step 2, let $T_s$ be $T$ at the start of the iteration and $T_e$ be $T$ at the end of the iteration and $e$ be the edge added to $S$. If $B$ doubly connects $T_e$, then $B\cup \{e\}$ doubly connects $T_s$.
2. In step 3, edges added in step 3 doubly connects $T$.
3. At the end of algorithm, $|S|=\lceil n/2\rceil$.

Exercise 3. Modify the algorithm so that no parallel edge is needed unless $n=2$.