2026-07-30T01:49:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23459 2025-10-02T12:55:45Z ddc:004 open_access

(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs Gahlawat, Harmender Rathod, Abhishek Zehavi, Meirav FPT Algorithms Kernelization T-Cycle Subexponential Algorithmms 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(√klog 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 klog^{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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Harmender Gahlawat and Abhishek Rathod and Meirav Zehavi 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.82 urn:nbn:de:0030-drops-234593 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.82 eng https://creativecommons.org/licenses/by/4.0/legalcode