@inproceedings{bib_Shor_2026, AUTHOR = {Chillara, Suryajith and Gajjar, Kshitij and G, Nithish Raja }, TITLE = {Shortest Paths with Linear Edge Weights}, BOOKTITLE = {Annual Symposium on Foundations of Computer Science}. YEAR = {2026}}

We study shortest paths in directed graphs whose edge weights are of the form $$ 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}inmathbb{R}$ is a fixed constant for each edge $e$, whereas each $lambda_i$ is a shared variable across the entire graph. So, there could 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 several combinatorial optimization problems. This is called the emph{Parametric Shortest Paths} problem, and has been studied since the 1980s. For $d=1$, Carstensen (1983) showed that the number of shortest paths in $n$-vertex graphs is at most $n^{O(log n)}$. She also proved a matching lower bound of $n^{Omega(log n)}$, which was later refined by Mulmuley & Shah (2001). For $d=2$, Gajjar & Radhakrishnan (2019) showed an upper bound of $n^{O(log^2 n)}$. Barth, Funke & Proissl (2022) generalized their result to prove an upper bound of $n^{O_d(log^d n)}$ for all positive integers $d$. The lower bound did not undergo any improvement over the years. In this paper, we close this long line of research by showing an $n^{O(dlog n)}$ upper bound for all positive integers $d$, exponentially improving the previous upper bound. We observe that a matching lower bound of $n^{Omega(dlog n)}$ can be obtained by trivially extending existing lower bound constructions for $d=1$. We also show that our proof can be adapted to work for undirected graphs with positive edge weights. 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})}$. Finally, building upon work on the emph{Point Location} problem by Ezra, Har-Peled, Kaplan & Sharir (2020), we construct a emph{Shortest Path Oracle} which takes as input a point $overline{x}in mathbb{R}^d$, and outputs a shortest path at $overline{lambda}=overline{x}$ in sublinear time (for a wide regime of $d$). All earlier upper bound proofs proceeded by arranging the vertices of the graph in layers, splitting the graph across its middle layer into two ``halves'', and then recursing on each half-graph. We deviate from this proof methodology by ``halving'' the graph in a different way: we eliminate all the odd-numbered layers and retain only the even-numbered layers, whilst maintaining requisite shortest paths of the original graph. We then view shortest paths in the half-graph as convex objects in $d$-dimensional space, which leads us to the required recurrence.

@inproceedings{bib_Mono_2024, AUTHOR = {Tengse, Anamay and Chatterjee, Prerona and Gajjar, Kshitij }, TITLE = {Monotone classes beyond VNP}, BOOKTITLE = {Theoretical Computer Science}. YEAR = {2024}}

In this work, we study the natural monotone analogues of various equivalent definitions of : a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than . We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone ( ) to be defined as the monotone analogue of Poizat's definition. With this definition, turns out to be exponentially stronger than and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš & Yehudayoff (2021). In that context, we show that transparent polynomials with large support are hard for the monotone analogues of all the known definitions of , except for the one due to Poizat.

@inproceedings{bib_Reco_2024, AUTHOR = {Kumar, Manish and Jha, Agastya Vibhuti and Lahiri, Abhiruk and Gajjar, Kshitij }, TITLE = {Reconfiguring Shortest Paths in Graphs }, BOOKTITLE = {Algorithmica}. YEAR = {2024}}

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming ), even for relaxed variants of the problem (assuming ). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most k (for a fixed integer ) contiguous vertices on a shortest path can be changed at a time.

@inproceedings{bib_Sum__2024, AUTHOR = {Fernau, Henning and Gajjar, Kshitij }, TITLE = {Sum labelling graphs of maximum degree two}, BOOKTITLE = {Discrete Mathematics}. YEAR = {2024}}

The concept of sum labelling was introduced in 1990 by Harary. A graph is a sum graph if its vertices can be labelled by distinct positive integers in such a way that two vertices are connected by an edge if and only if the sum of their labels is the label of another vertex in the graph. It is easy to see that every sum graph has at least one isolated vertex, and every graph can be made a sum graph by adding at most n2 isolated vertices to it. The minimum number of isolated vertices that need to be added to a graph to make it a sum graph is called the sum number of the graph. The sum number of several prominent graph classes (e.g., cycles, trees, complete graphs) is already well known. We examine the effect of taking the disjoint union of graphs on the sum number. In particular, we provide a complete characterisation of the sum number of graphs of maximum degree two, since every such graph is the disjoint union of paths and cycles

@inproceedings{bib_Reco_2024, AUTHOR = {Rusu, Irena and Chakraborty, Dibyayan and Gajjar, Kshitij }, TITLE = {Recognizing geometric intersection graphs stabbed by a line}, BOOKTITLE = {Theoretical Computer Science}. YEAR = {2024}}

In this paper, we determine the computational complexity of recognizing two graph classes, grounded 𝖫-graphs and stabbable grid intersection graphs. An 𝖫-shape is made by joining the bottom end-point of a vertical (|) segment to the left end-point of a horizontal (−) segment. The top end- point of the vertical segment is known as the anchor of the 𝖫-shape. Grounded 𝖫-graphs are the intersection graphs of 𝖫-shapes such that all the 𝖫-shapes’ anchors lie on the same horizontal line. We show that recognizing grounded 𝖫-graphs is 𝖭𝖯-complete. This answers an open question asked by Jelínek & Töpfer (Electron. J. Comb., 2019). Grid intersection graphs are the intersection graphs of axis-parallel line segments in which two vertical (similarly, two horizontal) segments cannot intersect. We say that a (not necessarily axis-parallel) straight line 𝓁 stabs a segment 𝑠, if 𝑠 intersects 𝓁. A graph 𝐺 is a stabbable grid intersection graph (S TAB GIG) if there is a grid intersection representation of 𝐺 in which the same line stabs all its segments. We show that recognizing S TAB GIG graphs is 𝖭𝖯-complete, even on a restricted class of graphs. This answers an open question asked by Chaplick et al. (Order, 2018).