(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913810202230784 |
|---|---|
| author | Gahlawat, Harmender Rathod, Abhishek Zehavi, Meirav |
| author_facet | Gahlawat, Harmender Rathod, Abhishek Zehavi, Meirav |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19301 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | (Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs Gahlawat, Harmender Rathod, Abhishek Zehavi, Meirav Data Structures and Algorithms Discrete Mathematics 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. |
| title | (Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2504.19301 |