Prof. Meirav Zehavi

Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, T -Cycle: given an undirected n-vertex graph G and a set of k vertices T ⊆ V (G) termed 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(√k log k⁾ · n-time fixed-parameter deterministic algorithm for T -Cycle on planar graphs; (ii) We provide a k^O(1) · n-time deterministic kernelization algorithm for 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 T -Cycle on planar graphs, as well as the first polynomial kernel for T -Cycle on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem.