A seminar titled ‘Isometric Path Complexity, Cover and related problems on (temporal) graphs’ was organised on Wednesday, 17 April, 2024 from 3:00 pm to 3:45 pm at MB 101.

Speaker: Dr. Dibyayan Chakraborty, a faculty member in the department of Computer Science at University of Leeds, UK. He also is an alumnus of this university.

Abstract:

Isometric path of a graph is a shortest path between its end-vertices. A collection of isometric paths is ”rooted” if all of them starts from the same vertex. Isometric path complexity (ipco (G)) of a graph G is the minimum number of ”rooted” isometric paths required to cover any isometric path of the graph. Even though this parameter was initially conceptualised to design constant factor approximation algorithms for a particular optimisation problem called “ISOMETRIC PATH COVER”, it was shown to be bounded for some interesting and seemingly different graph classes.

The talk discussed the known results and some techniques to bound isometric path cover on interesting graph classes. Then it explored how this parameter could be used to approximate ISOMETRIC PATH COVER. Later, it introduced the problem k-GEODESIC CENTER which was a qualitative relaxation of the ISOMETRIC PATH COVER, and present recent results on it. If time permited, some recent results on path covering problems on Temporal DAGs and trees, dynamic analogues of the usual DAGs and trees would also be presented. At the end, it would highlight some of the open problems that exist in this domain.