Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR18-211 | 4th February 2019 08:11

#### Parametric Shortest Paths in Planar Graphs

Revision #1
Accepted on: 4th February 2019 08:12
Keywords:

Abstract:

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

Changes to previous version:

This version of the paper differs from the version posted earlier in the following respects. (i) Some minor errors have been corrected. (ii) In the earlier version, the bound of $O((\log n)^3)$ on the bit lengths of the coefficients of the edge weights was argued informally; this version presents a formal argument. Furthermore, the coefficients are now integers, whereas earlier they were rational numbers. (iii) We attempt to provide a treewidth characterization for parametric shortest paths, which was not present in the earlier version. (iv) The appendix contains a proof that the parametric shortest path complexity of a $3 \times n$ grid graph is linear in $n$.

### Paper:

TR18-211 | 3rd December 2018 07:50

#### Parametric Shortest Paths in Planar Graphs

TR18-211
Publication: 12th December 2018 17:10
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.