planar graphs course homework 4

<2024-12-28 Sat 15:54:25>
cs homework uni2
\includepdf[pages=-]{homemahmooz/brain/notes/data/75/2eaf5e-9ee8-458f-b581-a37f5ec6e8a6/eden.pdf}
in class we discussed how to use MSSP to report the edges of shortest paths. in this problem you will work out the details of this data structure. assume you are given as a black box a data structure for the offline predecessor problem, in which we are given a set of elements, each with a distinct positive integer key bounded by some number . the data supports queries of the following form: given an integer return the predecessor of in . i.e., the element with largest key in whose key is at most (or null if none exists). it is easy to implement such a data structure with space and query time using a balanced BST, and it is known how to construct such a data structure with size and query time .
let be a planar embedded graph with infinite face whose vertices (in cyclic order) are denoted . describe in detail how to use the data structure for offline predecessor and the MSSP algorithm to build in time an -size data structure, so that given a pair of query vertices , the data structure outputs the arcs of an -to- shortest path in time, where is the number of edges of the path. you should describe exactly what the data structure stores, and how a query is answered. you may assume for simplicity that for each dart , there exist roots so that and . you do not have to prove the correctness of your data structure.
in class we described an algorithm for computing the breakpoints of an -by- monge matrix in time. the algorithm worked by adding one row at a time starting from the first row. we explained how this algorithm can be used to find the breakpoints in a lower triangular -by- monge matrix in time.
we did not describe in detail how to handle an upper triangular matrix. describe how to change the algorithm from class so that it works on an upper triangular monge matrix.
a student suggested the following different method for handling an upper triangular matrix. he suggested to turn the upper triangular matrix into a square monge matrix by implicitly filling in the elements of the lower triangular part as follows. for set , where is a number larger than any element of (see example below for ). then use the algorithm from class on the square matrix. does the student's solution work? explain briefly why.
(in reference to [[blk:dum-sssp-1]]).
we add the rows in reverse starting from the last row to the first, applying a symmetric procedure, after having applied the procedure for the last rows in the matrix (rows to ), let where be the nontrivial breakpoints of the rows we've handled, the comparison applied when adding the new row would become instead of for increasing values of (because we add rows backwards so it becomes instead of ), the rest of the procedure remains the same.
i substituted for (the original writing has the latter) because this way the notation aligns with that of fig-sssp-alg.
recall that in the shortest-paths with negative lengths algorithm we computed the distances in from a vertex on the separator to all other vertices of , and the distances in from to all vertices of . we then said that we can compute the distances in from to all vertices of by running dijkstra in with respect to the slack costs given by the price function and with the distances of the vertices of initialized to their distances from in , which are given by . i claim that doing this literally is incorrect.
  1. give an example where initializing the vertices of to their values in , and running Dijkstra with slack costs w.r.t. the price function would yield incorrect results.
  2. one way to overcome this problem is to add to arcs from to each vertex of with length corresponding to the -to- distance in . prove that even though these lengths can induce negative slack costs with respect to , running dijkstra's algorithm with respect to these slack costs on is correct. i.e., for every vertex of the distance computed is the true distance in minus . hint: recall that the correctness of dijkstra's algorithm can be established by showing that at the time a dart is relaxed, the distance label of has already been set to the correct -to- distance.
  3. another way to resolve this problem is to (1) remove all arcs entering , (2) add the same arcs as in (b), and (3) set the price function where is a number larger than the sum of absolute values of all dart lengths and remains unchanged for all other vertices of . prove that (1) the distances after these changes are the same as distances in , and that (2) the new definition of makes it feasible (i.e., induces non-negative slack costs).
  1. the problem mentioned in (a) is demonstrated below: /home/mahmooz/brain/pen/1736088089.0211134.xopp the respective slack costs for the lengths would be: the issue happens because we arent considering paths that branch out from into (or backwards) that may be shorter than any path enclosed in .
  2. /home/mahmooz/brain/pen/2025-01-08-Note-18-18.xopp dijkstra would start by relaxing all edges from to every other vertex (red edges in the drawing), once the edges are relaxed the vertices of would have the distance computed for them where would be negative if a shorter path exists outside , as we would have , but dijkstra would work anyway because those edges are relaxed first and other edges wont have negative costs, and being made smaller than it is wont change the outcome because the path from to whose distance is given by is already the shortest from to so there is no harm in decreasing its computed length if we only care about relative length results (in the shortest-path tree sense). note that because . since the issue described in (a) isnt present here (because all the shortest paths are now present in the graph passed to dijkstra a path can be made up of multiple ones that branch out from one to another and back). the correctness follows from the correctness of dijkstra, at any time step for an edge we would have is the length of the minimal path to , otherwise we would have missed some other simple path from to on the way to where , but this cant be possible because dijkstra grabs the vertex for which is smallest at each time step, the rest follows from the correctness of dijkstra. by a telescoping sum (lem-slack-cost-2) we obtain that the slack cost (and hence the distance computed by dijkstra) of a path from to is
  3. for some dart where we have is positive because is a from- price vector in and so slack costs with respect to are non-negative (by lem-slack-cost-1). if we may have (for the new edges): let represent the "duplicated" edges of , we have (we can think of it as ,) which means that , hence the expression of the slack cost is always non-negative. the proof of correctness is similar to the one given in the previous part of the problem (but here we have that the slack costs are positive, which doesnt matter in our case): dijkstra starts by relaxing all outgoing edges of which include the new edges, and so for every vertex we will have , but was initialized to anyway so it wouldnt change, then as described in the previous part since every edge of any possible simple path that crosses is contained in (each path that isnt closed in is represented by an edge that we added), and since the slack costs are all positive and are given by the modified from- price function ("modified" refers to the fact that ), we know that dijkstra will return the correct shortest path trees, because adding to all path costs will not affect the shortest path tree. we have which means that the actual cost of the path in from to some vertex can be reproduced by simply subtracting and from the respective slack cost.
in FR-Dijkstra, the amortized time analysis for implicitly assumed that at most one triplet is created with as the parent. however, our representation dictates that, if the interval of contains vertices that were already extracted from , 's interval should be broken down into many intervals that do not contain the extracted vertices. prove that when a vertex is activated, its interval does not contain extracted vertices.