(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs

Abstract

Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, \textsc{$T$-Cycle}: given an undirected $n$-vertex graph $G$ and a set of $k$ vertices $T\subseteq V(G)$ termed \textit{terminals}, the objective is to determine whether $G$ contains a simple cycle $C$ through all the terminals. Our contribution is twofold: (i) We provide a $2^{O(\sqrt{k}\log k)}\cdot n$-time fixed-parameter deterministic algorithm for \textsc{$T$-Cycle} on planar graphs; (ii) We provide a $k^{O(1)}\cdot n$-time deterministic kernelization algorithm for \textsc{$T$-Cycle} on planar graphs where the produced instance is of size $k{\log }^{O(1)}k$. Both of our algorithms are optimal in terms of both $k$ and $n$ up to (poly)logarithmic factors in $k$ under the ETH. In fact, our algorithms are the first subexponential-time fixed-parameter algorithm for \textsc{$T$-Cycle} on planar graphs, as well as the first polynomial kernel for \textsc{$T$-Cycle} on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem.

A short version pf this article will appear in ICALP 2025