How to increase the size of min-cut in graph by adding minimum number of edges

Question

Problem: Given a tree T = (V,E) . Add minimum number of edges so that even if one edge is removed from newly created graph still there is path from any vertex to any other vertex.

I believe the problem can be reduced to increasing the size of min-cut of graph to 2 from current min-cut of 1. But what will be an efficient algorithm to do so.

Answer 1

Here is algorithm, solving this problem for any undirected graph. It may be applied to a tree after some simplifications (step 1 is not needed).

1. Find all bridges in the graph with DFS or with Bridge-finding algorithm by Robert Tarjan.
2. Create a graph (in fact, it is a tree), where each bridgeless subgraph is substituted with a single vertex.
3. Collapse every chain in the tree into a single edge.
4. Find a path between two leaves (of length at least 3, when possible).
5. Pick any two vertices in subgraphs of the original graph, corresponding to both ends of this path, and connect them.
6. Collapse this path into a single vertex.
7. While there is more than one vertex in the tree, repeat from step 3.

Step 4 guarantees that we'll not get a new unneeded leaf after step 6, which is key to optimality.

Answer 2

Evgeny's solution is quite nice, but here's a simpler solution that works for Trees and whose correctness is easy to see.

Let L be the (original) leaves of the tree T. Let n be any node in the tree such that each of the subtrees obtained by removing n have at most |L|/2 original leaves. Note that it is always possible to find such a node n.

Let T₁, T₂, .. ,T_k be the subtrees obtained by removing n. Every original leaf (in L) is present in one of the T_is. Construct maximum disjoint pairs from the original leaves, with the constraint that the two original leaves in any pair belong to distinct subtrees. (This is conceptually same as constructing a maximum matching in a complete k-partite graph whose parts are the original leaves present in the subtrees).

If |L| is even, then every original leaf would be present in some pair and adding the edges corresponding to each of these pairs would make the resulting graph 2-connected. So we need to add |L|/2 edges in this case.

If |L| is odd, one original leaf would be not be paired, so we can connect this leaf to some arbitrary original leaf that is present in a different subtree. In this case we need to add (|L|+1)/2 edges.