School of Technology and Computer Science Seminars

Finding Optimal Shortest Path Trees

by Kshitij Gajjar (STCS, TIFR)

Friday, June 14, 2019 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
Abstract: Given a graph $G$ with one source vertex $s$ and several target vertices, a shortest path tree rooted at $s$ is a subgraph of $G$ that preserves distances from $s$ to each of the target vertices. A shortest path tree is called optimal if it has the minimum number of branching vertices (vertices of degree three or more). In this talk, we will see proofs of the following results.

1. Finding an optimal shortest path tree is $\mathsf{NP}$-hard for general graphs.
2. Finding an optimal shortest path tree is in $\mathsf{P}$ for interval graphs.

This is based on joint work with Jaikumar. A condensed version of this talk will be given at CSR 2019 in Novosibirsk, Russia.
Organised by Aditya Nema