| Title | : | Parametric Shortest Paths in Planar Graphs |
| Speaker | : | Jaikumar Radhakrishnan (TIFR, Mumbai) |
| Details | : | Fri, 8 Mar, 2019 4:00 PM @ Aryabhatta Hall (CSB |
| Abstract: | : | For a directed graph G with n vertices, including two
vertices s and t, and edge weights that vary linearly with a parameter
lambda, the cost of the shortest s-t path is a piece-wise linear
function of lambda. The number of pieces in this function is the parametric
shortest path complexity of G. We show that there is a sequence of
planar graphs, where the n-th graph has n vertices and parametric
complexity n^{c log n}, for a constant c > 0.
Graphs with similar parametric complexity were constructed by Carstensen (1983) and Mulmuley & Shah (2001) but their graphs were non-planar. Gusfield (1980) showed that the parametric complexity of an n vertex graph is at most n^{d log n}, for a constant d > 0, hence these constructions and ours are optimal. Nikolova, Kelner, Brand and Mitzenmacher (2006) conjectured that the parametric complexity of planar graphs is polynomially bounded; our construction refutes this conjecture. (This is joint work with Kshitij Gajjar, TIFR.) This is the 7th talk of the TCS-IIT Madras Computer Science and Engineering Colloquium Series. |
