ECCC-Report TR18-211https://eccc.weizmann.ac.il/report/2018/211Comments and Revisions published for TR18-211en-usMon, 04 Feb 2019 08:12:00 +0200
Revision 1
| Parametric Shortest Paths in Planar Graphs |
Kshitij Gajjar,
Jaikumar Radhakrishnan
https://eccc.weizmann.ac.il/report/2018/211#revision1We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ varies in $(-\infty,+\infty)$, the piece-wise linear cost of the shortest path from $s$ to $t$ has $n^{\Omega(\log n)}$ break points. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley & Shah (2000) for general graphs also hold for planar graphs. A conjecture of Nikolova (2009) states that the number of break points in $n$-vertex planar graphs is bounded by a polynomial in $n$; our result refutes this conjecture.
Gusfield (1980) and Dean (2009) showed that the number of break points for every $n$-vertex graph is $n^{\log n + O(1)}$ assuming linear edge weights; we show that if the edge weights are allowed to vary as a polynomial of degree at most $d$, then the number of break points is $n^{\log n + (\alpha(n)+O(1))^d}$, where $\alpha(n)$ is the slowly growing inverse Ackermann function. This upper bound is obtained by appealing to bounds on the length of Davenport-Schinzel sequences.Mon, 04 Feb 2019 08:12:00 +0200https://eccc.weizmann.ac.il/report/2018/211#revision1
Paper TR18-211
| Parametric Shortest Paths in Planar Graphs |
Kshitij Gajjar,
Jaikumar Radhakrishnan
https://eccc.weizmann.ac.il/report/2018/211We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ has $n^{\Omega(\log n)}$ break points. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley & Shah (2000) for general graphs also hold for planar graphs. A conjecture of Nikolova (2009) states that the number of break points in $n$-vertex planar graphs is bounded by a polynomial in $n$; our result refutes this conjecture.
Gusfield (1980) and Dean (2009) showed that the number of break points for an $n$-vertex graph is $n^{\log n + O(1)}$ assuming linear edge weights; we show that if the edge weights are allowed to vary as a polynomial of degree at most $d$, then the number of break points is $n^{\log n + O(\alpha(n)^d)}$, where $\alpha(n)$ is the slowly growing inverse Ackermann function. This upper bound arises from Davenport-Schinzel sequences.Wed, 12 Dec 2018 17:10:30 +0200https://eccc.weizmann.ac.il/report/2018/211