Subexponential Algorithms and Linear Kernels for Terminal Cycles in Planar Graphs

Title of the Talk: Subexponential Algorithms and Linear Kernels for Terminal Cycles in Planar Graphs
Speakers: Dr. Harmender Gahlawat
Host Faculty: Dr.Rogers Mathew
Date: Dec 15, 2025

Abstract: In this talk, I focus on a well-studied computational problem, $T$-Cycle: given an undirected n-vertex graph G and a set $T \subseteq V(G)$ of $k$ vertices called terminals, the objective is to determine whether $G$ contains a simple cycle passing through all vertices of $T$. I will present two algorithmic results for \textsc{$T$-Cycle} on planar graphs. First, I describe a deterministic fixed-parameter algorithm running in $2^{O(\sqrt{k}\log k)} \cdot n$ time. Second, I present a deterministic kernelization algorithm running in $k^{O(1)} \cdot n$ time that reduces any instance to an equivalent instance of size $k \log^{O(1)} k$. Both results are optimal up to polylogarithmic factors in $k$ under the Exponential Time Hypothesis. In particular, these are the first known subexponential-time fixed-parameter algorithm and the first polynomial kernel for \textsc{$T$-Cycle} on planar graphs, substantially improving the known results on the parameterized complexity of the problem.

Speaker Bio: Harmender is currently a postdoctoral researcher at Ben-Gurion University of the Negev, Israel, working in the group of Prof. Meirav Zehavi. He received his Ph.D. in computer science from ISI Kolkata in 2022 under the supervision of Prof. Sandip Das. Prior to joining BGU, he held postdoctoral positions at G-SCOP, Université Grenoble Alpes, and at LIMOS, Université Clermont Auvergne, France. His research interests lie primarily in the design and analysis of algorithms, with a focus on graph-searching games, terminal routing problems, fine-grained complexity of AI and ML, and graph metric covering.