Publications
(1) Distance-preserving Subgraphs of Interval Graphs
Authors: Kshitij Gajjar, Jaikumar Radhakrishnan
European Symposium on Algorithms (ESA), 2017
http://drops.dagstuhl.de/opus/volltexte/2017/7879/
(2) Minimizing Branching Vertices in Distance-preserving Subgraphs
Authors: Kshitij Gajjar, Jaikumar Radhakrishnan
Computer Science Symposium in Russia (CSR), 2019
Invited to special issue of Theory of Computing Systems (TOCS)
https://link.springer.com/chapter/10.1007/978-3-030-19955-5_12/
(3) Parametric Shortest Paths in Planar Graphs
Authors: Kshitij Gajjar, Jaikumar Radhakrishnan
Foundations of Computer Science (FOCS), 2019
Invited to Fine-grained Complexity Workshop (poster presentation), Tel Aviv Theory Fest, 2020
https://ieeexplore.ieee.org/document/8948673/
(4) Generalized Parametric Path Problems
Authors: Kshitij Gajjar, Girish Varma, Prerona Chatterjee, Jaikumar Radhakrishnan
Uncertainty in Artificial Intelligence (UAI), 2021
Selected for long talk at UAI
https://proceedings.mlr.press/v161/gajjar21a.html
(5) The Space Complexity of Sum Labelling
Authors: Henning Fernau, Kshitij Gajjar
Fundamentals of Computation Theory (FCT), 2021
https://link.springer.com/chapter/10.1007/978-3-030-86593-1_16/
Theory of Computing Systems (TOCS)
https://link.springer.com/article/10.1007/s00224-023-10130-2/
(6) Approximating the Center Ranking under Ulam
Authors: Diptarka Chakraborty, Kshitij Gajjar, Agastya Vibhuti Jha
Foundations of Software Technology & Theoretical Computer Science (FSTTCS), 2021
https://drops.dagstuhl.de/opus/volltexte/2021/15523/
(7) Finding Geometric Representations of Apex Graphs is NP-Hard
Authors: Dibyayan Chakraborty, Kshitij Gajjar
Conference and Workshops on Algorithms and Computation (WALCOM), 2022
https://link.springer.com/chapter/10.1007/978-3-030-96731-4_14/
Invited to special issue of Theoretical Computer Science (TCS)
https://www.sciencedirect.com/science/article/abs/pii/S0304397523003778/
(8) Reconfiguring Shortest Paths in Graphs
Authors: Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar, Abhiruk Lahiri
Conference on Association for the Advancement of Artificial Intelligence (AAAI), 2022
https://ojs.aaai.org/index.php/AAAI/article/view/21211/
(9) Monotone Classes Beyond VNP
Authors: Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse
Foundations of Software Technology & Theoretical Computer Science (FSTTCS), 2023
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.11/
(10) Sum Labelling Graphs of Maximum Degree Two
Authors: Henning Fernau, Kshitij Gajjar
Accepted, Discrete Mathematics (DM), 2023
Preprint: https://arxiv.org/abs/2301.02178/
(11) Recognizing Geometric Intersection Graphs Stabbed by a Line
Authors: Dibyayan Chakraborty, Kshitij Gajjar, Irena Rusu
Accepted, Theoretical Computer Science (TCS), 2024
Preprint: https://arxiv.org/abs/2209.01851/