Improved Algorithm for Diameter-Augmenting Paths in Metric Space

An Improved Algorithm for An Improved Algorithm for Diameter Augmenting Paths in a Augmenting Paths in a Metric Space Diameter- -Optimally Metric Space Optimally Haitao Wang Utah State University WADS 2017, St. John s, Canada

A path graph in a metric space A path graph in a metric space P: a path graph of n vertices v1, v2, , vn Each edge e(vi,vi+1) has a length |vivi+1| Assume all vertices are in a metric space Triangle inequality: |vivj| + |vjvk| |vivk|, for any three vertices vi, vj, vk What is the diameter of P? The length of the entire path between v1and vn |v2v4| + |v4v6| |v2v6| v7 v1 v2 v6 v3 v5 v4

The diameter The diameter- -optimally augmenting path problem optimally augmenting path problem Add an edge e(vi,vj) to connect two vertices vi and vj, so that the diameter of the resulting graph is minimized The length of the new edge is |vivj|, which can be obtained in O(1) time What is the diameter of the new graph? Previous work O(n log3 n) time, Gro e et al., ICALP 2015 Our result O(n log n) time v7 v1 v2 v6 v3 v5 v4

Related work Related work If P is in the Euclidean space Rd, for a constant d O(n+1/ 3) time to find a (1+ )-approximate solution, Gro e et al., ICALP 2015 If P is in the Euclidean plane R2 O(n) time, De Carufel et al. SWAT 2016 to minimize the continuous diameter, defined with respect to all points of P, not just the vertices For a geometric tree T of n vertices embedded in the Euclidean plane R2 O(n log n) time for continuous diameter, De Carufel et al. WADS 2017 Our problem is for discrete diameter in a metric space

Overview of our approach Overview of our approach *: the optimal objective value the diameter in an optimal solution The decision problem Given any value , determine whether *, determine whether we can add an edge to P so that the diameter is at most if yes, is called a feasible value Previous work: O(n log n) time, Gro e et al., ICALP 2015 Our result: O(n) time

Overview of our Overview of our approach: solving the original approach: solving the original optimization problem optimization problem Goal: compute * Previous work: parametric search, O(n log3 n) time, Gro e et al., 2015 Our approach Identify a set S of candidate values that contains * * is the smallest feasible value of S Find * in S, e.g., sort S and then binary search using the decision algorithm Difficulty |S| = (n2), cannot afford to compute S explicitly Our solution: Reduce the size of S in several steps Eventually |S| = O(n) and can be computed in O(n log n) time Each step takes O(n log n) time using our decision algorithm

The diameter of the new graph The diameter of the new graph G(i,j): the new graph after adding e(vi,vj) to P C(i,j): the cycle of G(i,j) D(i,j): the diameter of G(i,j) (i,j): the largest shortest path length from v1 to vkfor all i k j (i,j): the largest shortest path length from vn to vkfor all i k j (i,j): the shortest path length between v1 and vn (i,j): the largest shortest path length between vl and vkfor i l k j D(i,j) = max{ (i,j), (i,j), (i,j), (i,j)} vn v1 vi vj

Computing ( Computing (i,j i,j), ), ( (i,j i,j), ), ( (i,j i,j), ), ( (i,j i,j) ) With O(n) time preprocessing, for any (i,j) (i,j) can be computed in O(log n) time (i,j) can be computed in O(log n) time (i,j) can be computed in O(1) time How about (i,j)? (i,j) is the diameter of C(i,j) O(n) time, trivial but not good enough The main obstacle for solving the problem Call it -computation difficulty vn v1 vi vj

Solving the decision problem Solving the decision problem Given , determine whether is a feasible value Our approach For each 1 i n, determine whether there exists i j n, such that max{ (i,j), (i,j), (i,j), (i,j)}

Notation Notation Ii( ): the largest j such that (i,j) Ii( ): the smallest j such that (i,j) Ii( ): the smallest j such that (i,j) Ii( ): the largest j such that (i,j) (i,j) (i,j) (i,j) (i,j) j j Ii( ) Ii( ) Ii( ) Ii( )

Solving the decision problem Solving the decision problem For each i, determine whether there exists i j n, such that max{ (i,j), (i,j), (i,j), (i,j)} This is true iff there is a vertical line whose intersections with all four functions are below the horizontal line at which is true iff [1, Ii( )] [Ii( ),n] [Ii( ),n] [1,Ii( )] Computing Ii( ), Ii( ), Ii( ) for all 1 i n can be done in O(n) time This is not true for Ii( ) due to the - computation difficulty Ii( ) j Ii( )

Our algorithm Our algorithm Compute [1, Ii( )], [Ii( ),n],[Ii( ),n] for all 1 i n For each i, Whether Qi = [1, Ii( )] [Ii( ),n] [Ii( ),n] [1,Ii( )] is empty? If [1, Ii( )] [Ii( ),n] [Ii( ),n] = , then Qi is empty Else ai: the smallest index in [1, Ii( )] [Ii( ),n] [Ii( ),n] Observation: Qi is not empty iff (i,ai) How to determine whether (i,ai) ? Note: do not have to compute the exact value (i,ai) (i,j) j ai Ii( )

d(vk,vl): the shortest path length between vk and vl dP(vk,vl): the path length between vk and vl along P Determine Determine whether whether ( (i,a i,ai i) ) Determine whether the diameter of the cycle C(i,ai) is at most Whether d(vk,vl) , for all i k l ai A sub-problem: For each k, whether d(vk,vl) for all k l ai k : the smallest index with dP(vk,vk ) > Observation: Only need to check whether the length of the path from k to k containing the new edge is at most Check whether dP(vk,vk ) |C(i,ai)| - Sufficient to find the index k with the smallest dP(vk,vk ) O(1) time by a range-minima data structure Total time for the decision problem: O(n) k i ai k

The optimization problem The optimization problem Goal: compute *

The candidate sets The candidate sets D(i,j) = max{ (i,j), (i,j), (i,j), (i,j)} S = { (i,j) | 1 i j n} Define S , S , S similarly S = the union of the above four sets * must be in S * is the smallest feasible value of S |S| = (n2), too large to compute Our solution: Reduce the size of S in several steps Eventually |S| = O(n) and can be computed in O(n log n) time

Defining Defining , , , , , , : the smallest feasible value of S Define , , similarly * = min{ , , , } How to compute , , , ? The values of S can be organized into a sorted matrix so that each element can be computed in O(log n) time can be computed in O(n log n) time By a sorted matrix searching technique Using our decision algorithm This is also true for and , but not for due to the -computation difficulty S = S S S S

Computing Computing = min{ , , } Assumption: < *=

Notation Notation Ii( ): the largest j such that (i,j) Ii( ): the smallest j such that (i,j) Ii( ): the smallest j such that (i,j) Ii( ): the largest j such that (i,j) (i,j) (i,j) (i,j) (i,j) j j Ii( ) Ii( ) Ii( ) Ii( )

Define similar notation with respect to Define similar notation with respect to < < Computing I i( ), I i( ), I i( ) for all 1 i n can be done in O(n log n) time Not true for I i( ) due to the - computation difficulty I i( ): the largest j such that (i,j) < I i( ): the smallest j such that (i,j) < I i( ): the smallest j such that (i,j) < I i( ): the largest j such that (i,j) < (i,j) (i,j) (i,j) (i,j) j j I i( ) I i( ) I i( ) I i( )

A key observation A key observation Suppose e(i,j) is an optimal edge the edge added to P in an optimal solution *= = D(i,j) ai: the smallest index in [1, I i( )] [I i( ),n] [I i( ),n] Observation: j = ai Corollary: is the smallest feasible value of S ={ (i,ai)|1 i n} |S | = O(n) Compute in S Still cannot compute S in O(n log n) time due to the -computation difficulty Our solution: Follow the similar scheme as the decision algorithm Total time: O(n log n)

Thank you for your attention! Thank you for your attention!