Parametric Shortest Paths in Planar Graphs by Kshitij Gajjar

parametric shortest paths in planar graphs n.w
1 / 63
Embed
Share

Explore the concept of parametric shortest paths in planar graphs with insights provided by Kshitij Gajjar from Tata Institute of Fundamental Research, Mumbai. Understand the intricacies of directed, acyclic shortest paths in a visual and informative manner through detailed graphs and analysis presented in the images.

  • Parametric Graphs
  • Shortest Paths
  • Planar Graphs
  • Kshitij Gajjar
  • Tata Institute of Fundamental Research
rayaanacharya
more_ren Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Parametric Shortest Paths in Planar Graphs Kshitij Gajjar Tata Institute of Fundamental Research, Mumbai

  2. Shortest Paths Shortest Paths ?: directed, acyclic ?? ? = ??? ? ?1 ?4 ?2 ?5 ? ?3 ?6

  3. Shortest Paths Shortest Paths ? ?? ? = ??? ?1 ?4 ?2 ?5 ?3 ?6

  4. Shortest Paths Shortest Paths ? ?? ? = ?4 58 42 ?1 ?4 ? ?1 = 263 99 27 16 ? ?2 = 181 34 17 ? ?3 = 193 ?2 ?5 ? ?4 = 150 43 31 5 ? ?5 = 162 60 73 ? ?6 = 159 ?3 ?6

  5. Parametric Shortest Paths Parametric Shortest Paths ? ?? ? = ???! ! ! ? + 8 2? 5 ?1 ?4 7? 1 ? + 7 6? 2 4 5? 2? 4 ?2 ?5 4? + 3 ? 9 2? 1 5? + 6 ?3 ?6

  6. Parametric Shortest Paths Parametric Shortest Paths ? ?? ? = ???! ! ! ? + 8 2? 5 ?1 ?4 7? 1 ? + 7 ? ?1 = 10? + 8 6? 2 ? ?2 = 2? 7 4 5? ? ?3 = 8? + 6 2? 4 ?2 ?5 4? + 3 ? 9 ? ?4 = 7? 3 ? ?5 = 17? + 10 2? 1 5? + 6 ? ?6 = 13? + 4 ?3 ?6

  7. Parametric Shortest Paths Parametric Shortest Paths ? ?? ? ? ? + 8 2? 5 ?1 ?4 7? 1 ? + 7 ? ?1 = 10? + 8 6? 2 ? ?2 = 2? 7 4 5? ? ?3 = 8? + 6 2? 4 ?2 ?5 4? + 3 ? 9 ? ?4 = 7? 3 ? ?5 = 17? + 10 2? 1 5? + 6 ? ?6 = 13? + 4 ?3 ?6

  8. Parametric Shortest Paths Parametric Shortest Paths ? ?? ? 0 = ?2 ? + 8 2? 5 ?1 ?4 7? 1 ? + 7 ? ?1 = 10? + 8 6? 2 ? ?2 = 2? 7 4 5? ? ?3 = 8? + 6 2? 4 ?2 ?5 4? + 3 ? 9 ? ?4 = 7? 3 ? ?5 = 17? + 10 2? 1 5? + 6 ? ?6 = 13? + 4 ?3 ?6

  9. Parametric Shortest Paths Parametric Shortest Paths ? ?? ? 1 = ?2 ? + 8 2? 5 ?1 ?4 7? 1 ? + 7 ? ?1 = 10? + 8 6? 2 ? ?2 = 2? 7 4 5? ? ?3 = 8? + 6 2? 4 ?2 ?5 4? + 3 ? 9 ? ?4 = 7? 3 ? ?5 = 17? + 10 2? 1 5? + 6 ? ?6 = 13? + 4 ?3 ?6

  10. Parametric Shortest Paths Parametric Shortest Paths ? ?? ? 2 = ?1 ? + 8 2? 5 ?1 ?4 7? 1 ? + 7 ? ?1 = 10? + 8 6? 2 ? ?2 = 2? 7 4 5? ? ?3 = 8? + 6 2? 4 ?2 ?5 4? + 3 ? 9 ? ?4 = 7? 3 ? ?5 = 17? + 10 2? 1 5? + 6 ? ?6 = 13? + 4 ?3 ?6

  11. Cost of Path The shortest path sequence is (?) = (?1,?2,?3,?5,?6). ?6 This is a piece-wise linear concave function. ?4 We are interested in the number of break points, or, the number of times the shortest path changes. ?5 This is formally captured by . ?3 ?2 Break Points ?1 ?

  12. Definition Definition Given a graph ? and edge weights ?? that are linear functions of ?, the parametric shortest path complexity of ?, denoted by ?,??, is the number of break points in the cost of its shortest path. Let (?) be the maximum number of break points in the cost of the shortest path for an ?-vertex graph. ? = max ?,?? (?,??)

  13. Question Is ? finite? = (?1,?2,?1,?2, ). ?6 Answer Yes, it is finite. A shortest path once abandoned, cannot be reused. ?4 ?5 Thus, ? ?! exp(?). ?3 ?2 Break Points ?1 ?

  14. An Upper Bound for An Upper Bound for ?(?) A shortest path once abandoned, cannot be reused. The same holds true for subpaths as well (alternation-free property). Theorem [Gusfield, 1980] (?) ?log ?+?(1).

  15. Alternation Alternation- -free Sequences of Paths free Sequences of Paths Suppose = ?1,?2, ,?8, where A shortest path once abandoned, cannot be reused. ?1= ?,?,?,?,?,?,? ?2= ?,?,?,?,?,?,? ?3= ?,?,?,?,?,?,? ?4= ?,?,?,?,?,?,? ?5= ?,?,?,?,?,?,? ?6= ?,?,?,?,?, ,? ?7= ?,?,?,?,?,?,? ?8= ?,?,?,?,?, ,? Question Is this sequence alternation-free? Answer No.

  16. Alternation Alternation- -free Sequences of Paths free Sequences of Paths Suppose = ?1,?2, ,?8, where A shortest path once abandoned, cannot be reused. ?1= ?,?,?,?,?,?,? ?2= ?,?,?,?,?,?,? ?3= ?,?,?,?,?,?,? ?4= ?,?,?,?,?,?,? ?5= ?,?,?,?,?,?,? ?6= ?,?,?,?,?, ,? ?7= ?,?,?,?,?,?,? ?8= ?,?,?,?,?, ,? Question Is this sequence alternation-free? Answer No. There is a (?,?)-alternation in .

  17. Alternation Alternation- -free Sequences of Paths free Sequences of Paths Suppose = ?1,?2, ,?8, where A shortest path once abandoned, cannot be reused. ?1= ?,?,?,?,?,?,? ?2= ?,?,?,?,?,?,? ?3= ?,?,?,?,?,?,? ?4= ?,?,?,?,?,?,? ?5= ?,?,?,?,?,?,? ?6= ?,?,?,?,?, ,? ?7= ?,?,?,?,?,?,? ?8= ?,?,?,?,?, ,? Question Is this sequence alternation-free? Answer No. There is a (?,?)-alternation in .

  18. Alternation Alternation- -free Sequences of Paths free Sequences of Paths Suppose = ?1,?2, ,?8, where A shortest path once abandoned, cannot be reused. ?1= ?,?,?,?,?,?,? ?2= ?,?,?,?,?,?,? ?3= ?,?,?,?,?,?,? ?4= ?,?,?,?,?,?,? ?5= ?,?,?,?,?,?,? ?6= ?,?,?,?,?, ,? ?7= ?,?,?,?,?,?,? ?8= ?,?,?,?,?, ,? Question Is this sequence alternation-free? Answer No. The 3 paths ?1,?4,?8 constitute a (?,?)-alternation in .

  19. An Upper Bound for An Upper Bound for ?(?) Theorem [Gusfield, 1980] n ?log ?+?(1). Proof Let ?(?,?) be the maximum length of an alternation-free sequence of paths in an ?-vertex graph, where the paths are restricted to at most ? edges. ? ?,1 1 ?,? ? ?,? 2 ? 2 ? ? ?,? ?log ?+?(1)

  20. A Lower Bound for A Lower Bound for ?(?) Theorem [Carstensen, 1983] ? ? log ?. Theorem [Mulmuley, Shah 2001] ? ? log ?, where the coefficients of ?? have bit length ? log ?3.

  21. Planar Graphs Planar Graphs Theorem [Nikolova, Kelner, Brand, Mitzenmacher 2006] pl? (?). Theorem [Correa, Harks, Kreuzen, Matuschke 2017] sp? ? ? .

  22. Planar Graphs Planar Graphs Conjecture [Nikolova 2009] pl? ?? 1. Theorem [G, Radhakrishnan 2019] pl? ? log ?, where the coefficients of ?? have bit length ? log ?3.

  23. Planar Graphs Planar Graphs Theorem For every ? > 1,? > 1, there exists a planar graph ?? on ?42? vertices and an alternation-free sequence of paths in ?? such that | | ??. Corollary For every ? > 1, there exists a planar graph ?? on poly(?) vertices with an alternation-free sequence of paths in ?? such that | | ?log ?.

  24. Planar Graphs Planar Graphs Consider all the ?-digit base-? numbers in increasing order. 0 0 0 ?1= ?2= 0 0 1 ? = 4 ? = 3 . . . . . . ?64= 3 3 3 Each number corresponds to ? vertex-disjoint paths. Total ?? numbers = ??+1.

  25. The Layered Graph on a Cylinder The Layered Graph on a Cylinder ? vertices in each layer. 2? layers in all. ? = 4 ? = 3 ? ?

  26. The Layered Graph on a Cylinder The Layered Graph on a Cylinder ? vertices in each layer. 2? layers in all. ? = 4 ? = 3 ? ?

  27. The Layered Graph on a Cylinder The Layered Graph on a Cylinder ? ?

  28. The Layered Graph on a Cylinder The Layered Graph on a Cylinder ? ?

  29. The Layered Graph on a Cylinder The Layered Graph on a Cylinder ? ?

  30. Paths on a Cylinder Paths on a Cylinder planarize

  31. Alternation Alternation- -free Sequences of Paths in Planar Graphs free Sequences of Paths in Planar Graphs planarize

  32. Alternation Alternation- -free Sequences of Paths in Planar Graphs free Sequences of Paths in Planar Graphs planarize

  33. Alternation Alternation- -free Sequences of Paths in Planar Graphs free Sequences of Paths in Planar Graphs planarize

  34. Alternation Alternation- -free Sequences of Paths in Planar Graphs free Sequences of Paths in Planar Graphs planarize

  35. 1 0 2 2 ? ?

  36. 1 0 0 2 2 ? ?

  37. 1 0 0 2 2 ? ?

  38. 1 0 0 2 2 0 ? ?

  39. 1 0 2 2 0 0 ? ?

  40. 1 0 2 1 2 0 0 ? ?

  41. 1 0 2 1 2 1 0 0 ? ?

  42. 1 0 2 1 2 1 1 0 0 ? ?

  43. 1 0 2 1 2 1 1 1 0 0 ? ?

  44. 1 0 2 1 0 2 1 1 1 0 ? ?

  45. The The Carstensen Carstensen and and Mulmuley Mulmuley- -Shah framework Shah framework ??,? is a layered graph with ? source vertices. ?? ? 2?? The real line is divided into roughly ?? disjoint intervals. . . . ?? Each interval is assigned a path. ??,? . . . Those paths reign as shortest paths in their respective intervals. ?3 ?3 ?2 ?2 ?1 ?1 ??,? is built recursively.

  46. The decomposition of The decomposition of ??,? ? ?+? . . . . . . ?? 1,?+? ?? rev ?? 1,? ?? 1,? . . . . . . Link Gadget ? 3 ?3 ? 2 ?2 ?1 ? 1

  47. A step-by-step construction of ??,? for ? = 3, ? = 3, ? = 1. The gray area is the link gadget.

  48. The Link Gadget The Link Gadget planarize 1 unit Our link gadget is similar but planar. The Mulmuley-Shah gadget was a dense bipartite graph. ? ?+1 2 ? ?,? + ? = ?,? ?? ?? +? ?+1 ? ?,? + ? = ? ?,? + ? + ??? + ??? 2

  49. The Link Gadget The Link Gadget planarize 1 unit Our gadget is similar but planar. The Mulmuley-Shah gadget was a dense bipartite graph. ? ?+1 2 ? ?,? + ? = ?,? ?? ?? +? ?+1 ? ?,? + ? = ? ?,? + ? + ??? + ??? 2

  50. Properties of the Link Gadget Properties of the Link Gadget The edge weights are: ? ? + 1 2 ? ?,? + ? = ? ?,? + ? + ???, where 0 ? ? 1 and 0 ? ?, ? is a fixed function, ? and ? are large constants. The new edges thus created are assigned weights in proportion to their length.

Related


No related presentations.

More Related Content