2 citations · 4 across the 11 of their papers we have counts for
13 papers
Shortest Paths with Linear Edge Weights
Suryajith Chillara, Kshitij Gajjar, Nithish Raja
We study shortest paths in directed graphs whose edge weights are of the form Here…
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Kshitij Gajjar, Neeldhara Misra
We study a family of sorting match puzzles on grids, which we call permutation match puzzles. In this puzzle, each row and column of a grid is labeled with an ordering…
Parameterized Shortest Path Reconfiguration
Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri +1
An st-shortest path, or st-path for short, in a graph G is a shortest (induced) path from s to t in G. Two st-paths are said to be adjacent if they differ on exactly one vertex. A…
Sum Labelling Graphs of Maximum Degree Two
Henning Fernau, Kshitij Gajjar
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…
Recognizing Geometric Intersection Graphs Stabbed by a Line
Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu
In this paper, we determine the computational complexity of recognizing two graph classes, \emph{grounded L}-graphs and \emph{stabbable grid intersection} graphs. An L-shape is mad…
Monotone Classes Beyond VNP
Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran and Perifel 2009, Malod 2011, Mahajan…
Reconfiguring Shortest Paths in Graphs
Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar +1
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 pat…
The Space Complexity of Sum Labelling
Henning Fernau, Kshitij Gajjar
A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels i…
Finding Geometric Representations of Apex Graphs is NP-Hard
Dibyayan Chakraborty, Kshitij Gajjar
Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles (Koebe, 1936), line segments (Chalopin \& Gon{ç}alves, 2…
Generalized Parametric Path Problems
Prerona Chatterjee, Kshitij Gajjar, Jaikumar Radhakrishnan +1
Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general pa…
Parametric Shortest Paths in Planar Graphs
Kshitij Gajjar, Jaikumar Radhakrishnan
We construct a family of planar graphs , where has vertices including a source vertex and a sink vertex , and edge weights that change linearly…
Minimizing Branching Vertices in Distance-preserving Subgraphs
Kshitij Gajjar, Jaikumar Radhakrishnan
It is -hard to determine the minimum number of branching vertices needed in a single-source distance-preserving subgraph of an undirected graph. We show that this prob…
Distance-preserving Subgraphs of Interval Graphs
Kshitij Gajjar, Jaikumar Radhakrishnan
We consider the problem of finding small distance-preserving subgraphs of undirected, unweighted interval graphs with terminal vertices. To start with, we show that finding an…