Harmender Gahlawat

Hi! I’m currently a postdoctoral researcher in the LIMOS group at Université Clermont Auvergne (UCA), France, where I’m fortunate to work with Prof. Florent Foucaud.
Before this, I spent 2024 as a postdoc in the Combinatorial Optimization group at G-SCOP, Grenoble INP, France.
Earlier, from January 2022 to December 2023, I worked with Prof. Meirav Zehavi at Ben-Gurion University of the Negev, Israel.
I completed my Ph.D. at the Indian Statistical Institute, Kolkata, India.

My research interests lie broadly in Graph Searching, the Cops and Robber game, Parameterized Complexity, Path Covering and Packing problems, Approximation Algorithms, and the Theory of AI and ML.

Publications

Refereed Conference Publications:

1. - The Parameterized Complexity of Computing the VC-Dimension, with F. Foucaud, F. McInerny, and P. Tale, in NeurIPS 2025.
  - (Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs with A. Rathod and M. Zehavi, in ICALP 2025. Preprint version.
  - Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size with F. Fioravantes and N. Melissinos, in AAAI 2025. Preprint version.
  - Hunting a Rabbit is Hard with W. Ben-Ameur, and A. Maddaloni. in COCOON 2025. Preprint version.
  - The Closed Geodetic Game: Algorithms and Strategies with Z. M. Myint and A. Dailly, in IWOCA 2025. Preprint version.
  - Romeo and Juliet is EXPTIME-complete with J. M. Kristan and T. Valla, in MFCS 2024.
  - Learning Small Decision Trees with few Outliers: A Parameterized Perspective with M. Zehavi, in AAAI 2024. Preprint version.
  - Parameterized Complexity of Incomplete Connected Fair Division with M. Zehavi, in FSTTCS 2023. Preprint version.
  - Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs with J. Chaudhary, M. Wlodarczyk, and M. Zehavi, in IPEC 2023. Preprint version.
  - Parameterized Analysis of Cops and Robber Game with M. Zehavi, in MFCS 2023. Preprint version.
  - Monotonicity Helps a lot to Hunt a Rabbit with T. Dissaux, F. Fioravantes, and N. Nisse, in MFCS 2023. Preprint version.
  - Cops and Robber on Variants of Retracts and Subdivisions of Oriented Graphs (Brief Announcement) with Z. M. Myint and S. Sen, in LAGOS 2023. Preprint version.
  - Cops and Robber on Oriented Graphs with Respect to Push Operation with S. Das, A. Ramgopal, U.K. Sahoo, and S. Sen, in CALDAM 2023.
  - Complexity and algorithms for Isometric Path Cover on chordal graphs and beyond with D. Chakraborty, A. Dailly, S. Das, F. Foucaud, and S.K. Ghosh, in ISAAC 2022. Preprint version.
  - On the Cop number of String Graphs with S. Das, in ISAAC 2022.
  - Cops and Robber on Butterflies and Solid Grids with S.S Akhtar and S. Das, in CALDAM 2021.
  - Algorithms and Complexity for Geodetic Sets on Planar and Chordal Graphs with D. Chakraborty, S. Das, F. Foucaud, D. Lajou, and B. Roy, in ISAAC 2020.
  - Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes with D. Chakraborty, F. Foucaud, S.K. Ghosh, and B. Roy, in CALDAM 2020. Preprint version.
  - Cops and Robber game on some families of oriented graphs with S. Das, U.K. Sahoo, and S. Sen, in IWOCA 2019.
  - Bumblebee Visitation Problem with S. Das, in CALDAM 2019.
  - Variations of cops and robbers game on grids with S. Das, in CALDAM 2018.

Journal Publications:

1. - On the Cop Number of String Graphs with S. Das, in Electronic Journal of Combinatorics (In Production).
  - Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs with J. Chaudhary, M. Wlodarczyk, and M. Zehavi, in Journal of Computer and System Sciences 2025.
  - Further results on Hunters and Rabbit game through monotonicity with T. Dissaux, F. Fioravantes, and N. Nisse, in Information and Computation 2025.
  - Cops and Robber on Butterflies, Partial Grids, and AT-free graphs with S.S. Akhtar and S. Das. in Discrete Applied Mathematics 2024.
  - Algorithms and Complexity for Geodetic Sets on Partial Grids with D. Chakraborty and B. Roy. in Theoretical Computer Scince 2023.
  - Cops and Robber game on some families of oriented graphs with S. Das, U.K. Sahoo, and S. Sen, in Theoretical Computer Science 2022.
  - Variations of cops and robbers game on grids with S. Das, in Discrete Applied Mathematics 2021.
  - Bumblebee Visitation Problem with S. Das, in Discrete Applied Mathematics 2021.

Submitted Papers:

1. - Coarse Cops and Robber in Graphs and Groups with L. Esperet and U. Giocanti. Preprint version.
  - Pushing Cops and Robber on Graphs with Maximum Degree 4. Preprint version.

Teaching Experience

Teaching Assistantships

GIAN course on Sparse graphs: treewidth, planarity, bounded expansion, IIT Dharwad, GIAN course, Instructors: Prof. Florent Foucaud and Prof. Sagnik Sen. Duties: Teaching–4 hours (Lecture 1, Lecture 2), Tutorials–4 hours.

Data and File Structures, ISI Kolkata, M. Tech CS 1st year course, 2019, Instructor:Prof. Sandip Das. Duties: Teaching–3 hours, Tutorials–3 hours.

Programming and Data Structures Laboratory , ISI Kolkata, M. Tech CS 1st year course, 2018, Instructors: Prof. Ansuman Banerjee and Prof. Mandar Mitra. Duties: Lab assistant, Assignment design, grading, and tutorials–48 hours shared by 3 teaching assistants.

ACMU summer school on Algorithms and Optimization, ISI Kolkata, Summer School, 2017, Instructors: ACMU, ISI Kolkata staff. Duties: Tutorial/Problem Solving–6 hours shared by Dibyayan Chakraborty.

Discrete Mathematics, ISI Kolkata, M. Tech CS 1st year course, 2016, Instructor: Prof. Sandip Das. Duties: Tutorial–3 hours.

Student Supervisions

I have helped with the following student supervisions.

Student Name: Benjamin Court, Undergraduate Summer Intern at G-SCOP, Grenoble, 2024, Primary Mentor: Prof. Alantha Newman. Project: Approximation Algorithms for Metric Violation Distance

Student Name: Ashwin Ramgopal, Graduation Project, IIT Dharwad, 2021, Primary Mentor: Prof. Sagnik Sen. Project: Cops and Robber on Oriented Graphs with Push Operation (Publication)

Student Name: Sheikh Shakil Akhtar , Graduation Project, ISI Kolkata, 2020, Primary Mentor: Prof. Sandip Das. Project: Cops and Robber on Butterflies and Solid Grids, (Publication)

Talks

Cops, Robbers, and Representations: Exploring Graph Guarding Techniques. Venue: Indo-Spanish Pre-Conference School on Algorithms and Combinatorics, 2025 (InvitedTalk)
Monotonicity Helps a Lot to Hunt a Rabbit. Venue: ALCOLOCO Seminar UCA France 2024.

On the Cop Number of String Graphs. Venues: GGOAT Seminar CVUT, Prague 2023; Haifa Graphs and Combinatorics Workshop 2023; HALG 2023; GRASTA 2022. (Video Link)

Algorithms and Complexity for Isometric Path Cover . Venues: ISAAC 2022; HALG 2023.

Applications of Guarding Subgraphs to Cops and Robber Game. Venues: HOSIGRA Annual meeting 2021; COATI Seminar INRIA Sophia Antipolis 2021; ALCOLOCO Seminar UCA France 2021.