We are given an undirected graph weighted with positive arc lengthsand a distinguished edge $(a,b)$ in the graph. The problem is toreplace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a newnode, such that the length of the path $(a,c,b)$ is equal to theinital length of $(a,b)$, and such that the choice of the length of$(a,c)$ minimizes the maximum distance of node $c$ to any other nodeof the graph.  Is there any graph-theory based algorithm that can solve such problem rather than brute force?Actually, the existence of the original edge $(a,b)$ is notessential. Only the end nodes $a$ and $b$, and the length matter.For example we have a graph:1 2 102 3 103 4 14 1 5In every line the first two values indicate the node number, and the 3rd one is the corresponding edge value. Now I want to find a new node $c$ between nodes 1 and 2. The answer givesa node $c$ at distance 2 to node 1 (and distance 8 to node 2). Thedistance of node $c$ is 2 to node 1, 8 to node 2, 1+5+2=8 to node 3, and5+2=7 to node 4. The maximum distance is 8, which is minimal for allpossible choices of the length of $(a,c)$.
Adding a node between two others, minimizing its maximum distance to any other node
algorithms;graphs;graph theory;shortest path;weighted graphs
IntroductionThis answer is in two parts.The first is an analysis of the problem mixed with a sketch of thealgorithm to solve it. As it is my first version, it is detailed, butresults in an algorithm that is a bit more complex than needed.It is followed by a pseudo-code version of the algorithm, written sometime later, as the algorithm was clearer. This pseudo-code is moredirect, and somewhat simpler, but probably easier to understand afterreading the first part.In retrospect, the more important ideas are:to see that the maximum distance of a node to the new node C, as afunction of the length of $(A,C)$, is given by the superposition ofroof shaped (inverted V) curves, characterized by their top,associated to nodes of the graph.to see that irrelevant curves can be eliminated efficiently by ascan in monotonic order of abscissa of tops (with minimum backtrack).then minimal points can be enumerated simply by intersecting the remainingcurves two by two, again in monotonic order of abscissa of tops.Sketch of an algorithmNOTE: I changed the initial presentation of the question to get a morestandard view of graphs, by considering that the edge $(A,B)$ isreplaced by a new node $C$ and two edges $(A,C)$ and $(C,B)$ with thesame total length as $(A,B)$.Let $(A,B)$ be the distinguished edge, and let $l$ be its length. Let$e$ and $n$ be respectively the number of edges and the number ofnodes in the graph.First you remove the edge $(A,B)$. Then, for every node $U$ of thegraph, you compute the distance $\alpha(U)$ between $A$ and $U$, andthe distance $\beta(U)$ between $B$ and $U$. This can be done withDijkstra's shortest path algorithm, in time $O(e+n\log n)$.Then you add a new node $C$ with an edge $(A,C)$ and an edge $(C,B)$,of length respectively $a$ and $b$, such that $a+b=l$. Thelength $a$ is not known, and is to be found so as to minimize thedistance of the most remote node to node $C$. The distance of $C$ to$A$ or $B$ may be 0.The difficulty of the problem is that the node most distant from $C$via $A$ may be close to $C$ via $B$, and thus does not matter. Also, anode closer to $C$ via $A$ than via $B$ may inverse that situation as$C$ moves between $A$ and $B$, i.e. as $a$ varies in $[0,l]$.We consider three sets of nodes in the graph, forming a partition ofall nodes:the set $N_A$ of nodes that are always closer to $C$ via $A$independently of the value of $a$:$N_A=\{U|\alpha(U)+l\leq\beta(U)\}$the set $N_B$ of nodes that are always closer to $C$ via $B$ independentlyof the value of $a$:$N_B=\{U|\beta(U)+l\leq\alpha(U)\}$and $N_{AB}$ the set of nodes that can be closer to $C$ via $A$ orvia $B$, depending on the value of $a$, actually closer via $A$ forsmaller values of $a$, and closer via $B$ for larger values of $a$ in $[0,l]$:$N_{AB}=\{U\mid\alpha(U)+l>\beta(U) \wedge \beta(U)+l>\alpha(U)\}$Let $U_A$ the node in $N_A$ most remote from $A$, and $U_B$ the nodein $N_B$ most remote from $B$.No other node in $N_A\cup N_B$ is ever more distant from $C$ than themore distant of these two nodes, whatever the distance $a$ of $(A,C)$.Hence all other nodes in $N_A\cup N_B$ can be discarded for thecomputation of the optimal value of $a$.Note that it may happen that $N_A$, or $N_B$, or both, are empty. Inwhich case, the corresponding nodes $U_A$ and/or $U_B$ do not exist.We will build a distance curve on a plane with coordinate $(x,y)$, which willultimately represent the longest distance $y$ of a node from $C$ as afunction of the distance $x=a$ of $C$ from $A$. Hence $x=a\in[0,l]$This distance curve is actually a zig-zag composed of segments angled $\pm45^\circ$. Once it is built, the point minimizing the longest distanceis to be found in the minimal points of the curve. There may beseveral such points. All these points have to be computed, and thencompared.We describe below how to compute them.Actually, we consider a collection of simpler distance curves, with only one ortwo segments in the interval $[0,l]$, such that the longest distance ofa node from $C$ is always on or above the curve. The final curve isobtained by taking for every value of $x$ the maximum value of $y$given by one of the distance curves. This can be done formally by computing theintersection of the segments in an ordered fashion.First we have (at most) two distance curves composed of only one segment. Theseare the curves corresponding to the distance of $U_A$ and $U_B$ to$C$. The first is upward at a $45^\circ$ angle, and the second isdownward at a $45^\circ$ angle.Assuming no other node is ever more distant from $C$, the optimalvalue of $a$ is the abcissa of their intersection. At that abscissa,that value for $a$, the nodes $U_A$ and $U_B$ are at the same distancefrom $C$. Hence the distance is minimum when $a$ satisfies theequation $\alpha(U_A)+a=\beta(U_B)+b$. Since $a+b=l$, this gives$\alpha(U_A)+a=\beta(U_B)+l-a$, and finally$a=(\beta(U_B)-\alpha(U_A)+l)/2$. This corresponds to a distance$y=(\alpha(U_A)+\beta(U_B)+l)/2$ of both nodes to $C$.Together, the two curves give a V shaped curve, with a minimum at thepoint just computed.But we also have to account for all the nodes in $N_{AB}$. Thedistance of a node $U\in N_{AB}$ to $C$ first increases with $x$ whilethe shortest path goes through $A$, them it decreases with $x$ whenthe shortest path goes through $B$. Hence, the corresponding distance curve isformed of two segments, roof shaped, with a maximum at an abscissasuch that the distance to $C$ is the same through $A$ or through $B$.This gives the equation $\alpha(U)+a=\beta(U)+b$. Resolving it asabove, we get $x=a=(\beta(U)-\alpha(U)+l)/2$, and$y=\alpha(U)+\beta(U)+l)/2$. We note $T_U$ (for Top of $U$) the pointwith these coordinate. The top $T_U$ characterizes the roof shaped distancecurve for node $U$ since the slope of both side is $\pm 45^\circ$.Now all the difficulty of the problem is that several nodes $U\inN_{AB}$ may be such that $T_U$ is above our first V-shaped curve,which will lead to the final zig-zag line.But, we first can eliminate all nodes $U\in N_{AB}$ such that $T_U$ isbelow the V-shaped distance curve, as they will not ever contribute to thelongest distance. This is easily done and is skipped here for clarity.Then we want also to eliminates all nodes $U\in N_{AB}$ such thattheir roof-shaped curve is always below the curve of another node$V\in N_{AB}$. This is determined by the position of their tops, andwe say that $T_V$ dominates $T_U$, or that $V$ dominates $U$. Actually$T_V$ and $T_U$ are in a domination relation iff the absolute valueof the abcissa difference is less than the absolute value of theordinate difference. The dominating node/top is the one with thehighest ordinate.For this purpose, we first sort all tops of the remanining nodes of$N_{AB}$ in ascending order of increasing abscissa. This is done intime $O(n\log n)$.Then we remark that if top $T_U$ dominate a non adjacent top $T_V$,then any intermediary top $T_W$ dominate $T_V$, or is dominated by$T_U$, or both. Hence, to eliminate all nodes/tops that are dominated,on can simply proceed from left to right (by increasing abscissa),comparing only adjacent nodes, and removing any that is dominated.  Ifthe node on the right is dominated, it is removed and the node on theleft is compared again to the next right. If the node on the left isdominated, it is removed and the node on the right is then comparedwith the previous one on its left. If none dominates the other, then the node on leftis kept, and the node on rightis then compared with the next right. This is repeated until therightmost node/top has been thus processed, in time $O(n)$.Whatever nodes have been kept do contribute to the final curve, inleft to right order of their tops, with the line for $U_A$ at the leftand the line for $U_B$ at the right, if they exist. The minima areeasy to compute by considering the intersections of the contributingcurves from left to right, in time $O(n)$.Finally, the abcissa for the smallest distance of all nodes to $C$ may befound by a linear scan of all minima for the lowest ones. They mayactually be several such abscissa, i.e. values for the length $a$ ofedge $(A,C)$.If the distances have to be integers, the abscissa of the minima can berounded up or down.The time complexity of the algorithm is: $O(e+n\log n)$.With thanks to user3153970 who remarked that my initial solution wasnot quite correct.Pseudo-code versionThe procedure described in the analysis of the problem is modified orimproved in some ways.the length l is changed to d to avoid confusion with the number 1.for simplification, the V curve is replaced by two tops of roof curves placed onboth end of the interval [0,d].the sets $N_A$ and $N_B$ need not be created. Only $d_A$ and $d_B$are needed, briefly, to crate the two extra tops.the set $N_AB$ is not created either, only the corresponding set(actually a multiset, or bag, that may be implemented as a list) of tops, as two distinct nodes mayproduce the same top, if at the same distance of A and B.(bugs are provided free of charge)d := distance (A,B)  none := -1     % programming trick - none is for distances to be ignored %Remove the edge (A,B) from the graph.  Using Dijkstra's shortest path algorithm, for every node $U$ compute its shortest    distances (U) and (U) to respectively A and B.  d_A := noned_B := none  % We use lists of pairs, representing the [x,y] coordinate of points, where the %  % abcissa x stands for the choice of length (A,C), and the ordinate y stands is the %  % distance of some node to C. %  % The call first(L) returns a pointer to the first pair of list L. %  % Given a pointer t to a pair, t.x and t.y give the two components of the pair, %  % and the functions prev and next return a pointer to the previous or the next pair, or %  % NIL if it does not exist. The call add([a, b], L) adds the pair [a, b] to the list L. %  % The call remove(t) removes the element pointed by t from its list. %For every node U do   T := []     % T is the list of tops of curves for individual nodes %      if    (U)+d  (U) then d_A := max(d_A, (U))       elsif (U)+d  (U) then d_B := max(d_B, (U))       else add( [((U)-(U)+d)/2, ((U)+(U)+d)/2], T)% Instead of V curve, create dummy tops at ends of [0,d] interval %if d_A none then add( [d, d_A+d], T)if d_B none then add( [0, d_B+d], T)Sort T in increasng order of abscissa% Remove from T all tops that are dominated by another top %t1 := first(T)t2 := next(t1)Repeat    if abs(t1.x-t2.x) abs(t1.y-t2.y)    then  % one top dominates the other %        if t1.yt2.y            then  % t1 dominates %            remove(t2)            t2 := next(t1)            if t2=NIL then exit loop        else % t2 dominates %            remove(t1)            t1 := pred(t2)            if t1=NIL then                t1 := t2;                 t2 := next(t1)                if t2=NIL then exit loop     else % neither top dominate the other %         t1 := t2         t2 := next(t1)         if t2=NIL then exit loop% Compute all local minima %M := []  % M is the list of minima, where roof shaped curves intersect, %         % or intersect the boundaries of the interval [0.d]. %t2 := first(T);if t2.x0 then add( [0, t2.y-t2.x], M)repeat    t1 := t2    t2 := next(t1)    if t2=NIL then exit loop    add( [(t1.y-t2.y+t1.x+t2.x)/2, (t1.y+t2.y+t1.x-t2.x)/2], M)if t2.xd then add( [d, t2.y-d+t2.x], M)Select in M the pairs with the smallest ordinates. Their abcissas are all    the possible answers to the problem.If the solutions must be in integer values, it is possible to roundthe coordinates of the points in M to the nearest integer(s), beforeselecting the pairs with smallest ordinates. However some moreanalysis is needed to check whether it can involve passing over a top,and whether abcissas and ordinates are always integer simultaneously.This is left to the reader as an exercise.All bug reports are welcome.