Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-211 | 3rd December 2018 07:50

Parametric Shortest Paths in Planar Graphs


Authors: Kshitij Gajjar, Jaikumar Radhakrishnan
Publication: 12th December 2018 17:10
Downloads: 131


We 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.

ISSN 1433-8092 | Imprint