BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1755
DTSTAMP:20260825T065147Z
SUMMARY:Shortest Paths with Linear Edge Weights
DESCRIPTION:Speaker: Suryajith Chillara (IIIT Hyderabad)\n\nAbstract: \n\nW
 e study shortest paths in directed graphs whose edge weights are of the fo
 rm $ \\mathsf{wt}(e) = a_{e\,1} \\lambda_1 + a_{e\,2} \\lambda_2 + a_{e\,3
 } \\lambda_3 + \\cdots + a_{e\,d} \\lambda_d + a_{e\,d+1}.$ Here\, each $a
 _{e\,i}\\in\\mathbb{R}$ is a fixed constant for each edge $e$\, whereas ea
 ch $\\lambda_i$ is a shared variable across the entire graph. So\, there c
 ould be different shortest paths in the graph for different values of the 
 $\\lambda_i$'s. The number of such shortest paths is of interest in severa
 l combinatorial optimization problems. This is called the \\emph{Parametri
 c Shortest Paths} problem\, and has been studied since the 1980s.\n    
 \nFor $d=1$\, Carstensen (1983) showed that the number of shortest paths i
 n $n$-vertex graphs is at most $n^{O(\\log n)}$. She also proved a matchin
 g lower bound of $n^{\\Omega(\\log n)}$\, which was later refined by Mulmu
 ley \\& Shah (2001). For $d=2$\, Gajjar \\& Radhakrishnan (2019) showed an
  upper bound of $n^{O(\\log^2 n)}$. Barth\, Funke \\& Proissl (2022) gener
 alized their result to prove an upper bound of $n^{O_d(\\log^d n)}$ for al
 l positive integers $d$. The lower bound did not undergo any improvement o
 ver the years.\n \nIn this paper\, we close this long line of research by
  showing an $n^{O(d\\log n)}$ upper bound for all positive integers $d$\, 
 exponentially improving the previous upper bound. We observe that a matchi
 ng lower bound of $n^{\\Omega(d\\log n)}$ can be obtained by trivially ext
 ending existing lower bound constructions for $d=1$. We also show that our
  proof can be adapted to work for undirected graphs with positive edge wei
 ghts. Furthermore\, for directed graphs whose edge weights are univariate 
 polynomials of degree at most $q$\, we prove an upper bound of $n^{O(\\log
 {n}+\\log{q})}$.\n \nJoint work with Kshitij Gajjar and Nithish Raja.\n(h
 ttps://arxiv.org/abs/2607.21055)\n
URL:https://www.tcs.tifr.res.in/web/events/1755
DTSTART;TZID=Asia/Kolkata:20260825T160000
DTEND;TZID=Asia/Kolkata:20260825T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR