Speaker: |
Kshitij Gajjar |

Organiser: |
Vinod M. Prabhakaran |

Date: |
Friday, 4 Jan 2019, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

(i) Given a graph with $k$ special vertices (called terminals), a distance-preserving subgraph of it is a subgraph which has the same pairwise distances between the terminals as in the original graph. We prove that every interval graph with $k$ terminals has a distance-preserving subgraph with $O(k \log k)$ vertices of degree three or more. We also prove that this bound is tight.

(ii) Given a graph with two special vertices $s$ and $t$, and edge weights that vary linearly with a parameter $\lambda$, the parametric shortest path complexity of the graph is the number of times the shortest $s$-$t$ path changes as $\lambda$ varies from $-\infty$ to $+\infty$. We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices, such that the parametric shortest path complexity of $G_n$ is $n^{\Omega(\log n)}$. This refutes a conjecture of Nikolova (2009).