Harmender Gahlawat: Subexponential Algorithms and Linear Kernels for Terminal Cycles in Planar Graphs
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 \(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 \(T\)-Cycle on planar graphs, substantially improving the known results on the parameterized complexity of the problem.