Optimal Bridge, Twin Bridges and Beyond: Inserting Edges into a Road Network to Minimize the Constrained Diameters

Given a road network modelled as a planar straight-line graph $G=(V,E)$ with $|V|=n$, let (u,v)∈ V× V, the shortest path (distance) between $u,v$ is denoted as δG(u,v). Let δ(G)=max(u,v)δG(u,v), for (u,v)∈ V× V, which is called the diameter of G. Given a disconnected road network modelled as two disjoint trees T₁ and T₂, this paper first aims at inserting one and two edges (bridges) between them to minimize the (constrained) diameter δ(T₁∪ T₂∪ Iⱼ) going through the inserted edges, where Iⱼ, j=1,2, is the set of inserted edges with |I₁|=1 and |I₂|=2. The corresponding problems are called the { optimal bridge} and { twin bridges} problems. Since when more than one edge are inserted between two trees the resulting graph is becoming more complex, for the general network G we consider the problem of inserting a minimum of k edges such that the shortest distances between a set of m pairs P=\(uᵢ,vᵢ) uᵢ,vᵢ∈ V, i∈ [m]\, δG(uᵢ,vᵢ)'s, are all decreased. The main results of this paper are summarized as follows: (1) We show that the optimal bridge problem can be solved in O(n²) time and that a variation of it has a near-quadratic lower bound unless SETH fails. The proof also implies that the famous 3-SUM problem does have a near-quadratic lower bound for large integers, e.g., each of the n input integers has Ω(log n) decimal digits. We then give a simple factor-2 O(nlog n) time approximation algorithm for the optimal bridge problem. (2) We present an O(n⁴) time algorithm to solve the twin bridges problem, exploiting some new property not in the optimal bridge problem. (3) For the general problem of inserting k edges to reduce the (graph) distances between m given pairs, we show that the problem is NP-complete.