(Almost-)Optimal FPT Algorithm and Kernel for T T -Cycle on Planar Graphs
Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi · 2025
Read (Almost-)Optimal FPT Algorithm and Kernel for T T -Cycle on Planar Graphs by Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19301.txt.
Introduction
Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi solve a graph problem on flat maps in a 2025 paper. The problem asks whether a network drawn without crossings holds a single loop passing through every marked terminal point, a puzzle at the heart of graph theory.
Their contribution is twofold. They give a deterministic algorithm whose running time grows far more gently with the number of terminals than brute force would. They also give a compression routine that shrinks any instance to a size barely above the terminal count, without changing the answer. Both are the first of their kind for this problem and are provably near-best under standard assumptions, up to small factors.
Catalog record
| CREATOR | Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 123 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19301
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
(Almost-)Optimal FPT Algorithm and Kernel for T T -Cycle on Planar Graphs Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi 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, T T -Cycle : given an undirected n n -vertex graph G G and a set of k k vertices T ⊆ V ( G ) T\subseteq V(G) termed terminals , the objective is to determine whether G G contains a simple cycle C C through all the terminals. Our contribution is twofold: (i) We provide a 2 O ( k log k ) ⋅ n 2^{O(\sqrt{k}\log k)}\cdot n -time fixed-parameter deterministic algorithm for T T -Cycle on planar graphs; (ii) We provide a k O ( 1 ) ⋅ n k^{O(1)}\cdot n -time deterministic kernelization algorithm for T T -Cycle on planar graphs where the produced instance is of size k log O ( 1 ) k k\log^{O(1)}k . Both of our algorithms are optimal in terms of both k k and n n up to (poly)logarithmic factors in k k under the ETH. In fact, our algorithms are the first subexponential-time fixed-parameter algorithm for T T -Cycle on planar graphs, as well as the first polynomial kernel for T T -Cycle on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem. 1 Introduction Combinatorial properties of (simple) cycles passing through a specific set of vertices (along with, possibly, other vertices) in a graph—and, in particular, combinatorial properties of the graphs containing them—have been intensively explored for over six decades. As observed by Björklund et al. [ 7 ] , the public interest in this topic can even be dated back to 1898, when Lewis Carroll challenged the readers of Vanity Fair with a riddle linked to this problem. However, the flurry of scientific results on this topic has, roughly, begun with Dirac’s result [ 16 ] from 1960, stating that given k vertices in a k -connected (undirected) graph G , G has a cycle through all of them. For a few illustrative examples of works in Graph Theory that followed up on this result, we refer to [ 10 , 24 , 26 , 45 , 18 , 40 , 41 , 23 , 25 ] . Indeed, as stated by Kawarabayashi [ 27 ] : “Since 1960’s, cycles through a vertex set or an edge set are one of central topics in all of graph theory.” Computationally, given an undirected n -vertex graph G and a set of k vertices T\subseteq V(G) referred to as terminals (for any k\in\{1,2,\ldots,n\} ), the objective of the T -Cycle problem is to determine whether G contains a (simple) cycle C that passes through all (but not necessarily only) the terminals. Henceforth, such a cycle is referred to as a T -loop . Due to the immediate relation between the T - Cycle and Disjoint Paths problems (formalized later in this introduction), the T -Cycle problem has been long known (since the seminal work of Robertson and Seymour [ 39 ] ) to be fixed-parameter tractable , that is, solvable in time f(k)\cdot n^{c} for some computable function f of k and some fixed constant c . However, here, the best known f is galactic, satisfying f(k)\geq 2^{2^{2^{2^{2^{k}}}}} , and c=2 [ 28 ] . Still, already in 1980, LaPaugh and Rivest [ 33 ] provided a linear time algorithm for T -Cycle when k=3 , which involved no large hidden constants. The first breakthrough for the general case—having k as part of the input—was established in 2008 by Kawarabayashi [ 27 ] , who proved that: 1 1 1 Kawarabayashi [ 27 ] states that when k is a fixed constant, the dependency on n in the runtimes of his algorithms can be made linear, but no details of a proof to support this statement are given. • The T -Cycle problem is solvable in time 2^{2^{O(k^{10})}}\cdot n^{2} . We remark that using the developments in [ 12 ] on the Grid-Minor Theorem that were first published shortly after the work of Kawarabayashi, it can be easily seen that his algorithm can be made to run in time 2^{O(k^{c})}\cdot n^{2} for some large constant c . • Restricted to planar graphs, the T - Cycle problem is solvable in time 2^{O(k\log^{4}k)}\cdot n^{2} . We note that all algorithms mentioned so far are deterministic. In 2010, by making novel use of the idea behind the breakthrough technique of algebraic fingerprints [ 5 , 6 ] , Björklund et al. [ 7 ] developed a randomized algorithm for T -Cycle that runs in time O(2^{k}\cdot n) , which, prior to this manuscript, has remained the fastest known algorithm for this problem even if restricted to planar graphs. We note that however, prior to this manuscript, both of Kawarabayashi’s algorithms have remained the best-known deterministic ones for the problem even if restricted to planar graphs. With the above context in mind, the first of the two main contributions of our manuscript can be summarized in the following theorem. Specifically, we present the first subexponential-time fixed-parameter algorithm for the T -Cycle problem on planar graphs. Theorem 1 . Restricted to planar graphs, the T -Cycle problem is solvable in time 2^{O(\sqrt{k}\log k)}\cdot n . Notably, under the Exponential Time Hypothesis (ETH), the time complexity in Theorem 1 is tight up to the logarithmic factor in the exponent, and, on general graphs, no sub-exponential-time (fixed-parameter or not) algorithm exists for T -Cycle . This can be seen from the fact that Hamiltonicity is the special case of T -Cycle when T is the entire vertex set of the graph, and Hamiltonicity is not solvable in times 2^{o(\sqrt{n})} and 2^{o(n)} on planar and general graphs, respectively, under the ETH [ 14 ] . The existence of a subexponential-time fixed-parameter algorithm for the T -Cycle problem on planar graphs might seem surprising when considered in the context of two other well-known “terminals-based” problems on planar graphs: Specifically, under the ETH, the Steiner Tree problem on planar graphs is not solvable in time 2^{o(k)}\cdot n^{O(1)} [ 36 ] , and the Disjoint Paths problem was only recently shown to be solvable in time 2^{k^{O(1)}}\cdot n [ 13 ] , where, in both cases, k denotes the number of terminals. Following-up on the work of Björklund et al. [ 7 ] , Wahlström [ 43 ] studied the compressability of T -Cycle . To discuss Wahlström’s contribution, let us first present the definitions of compression and kernelization. Formally, we say that a (decision) parameterized problem \Pi admits a compression into a (decision, not necessarily parameterized) problem \Pi^{\prime} if there exists a polynomial-time algorithm (called a compression algorithm ) that, given an instance (I,k) of \Pi , produces an equivalent instance J of \Pi^{\prime} such that |J|\leq f(k) for some computable function f of k . When f is polynomial, then the compression is said to be polynomial-sized (or, for short, polynomial ), and when \Pi^{\prime}=\Pi , then the compression is termed kernelization . Kernelization is, perhaps, the most well-studied research subarea