跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2609.24804 · v2

FPT Isomorphism Test for $F$-Free Tournaments

首次提交 2026-09-22 00:01
版本更新 2026-11-18 19:29
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

We show that isomorphism of FF-free tournaments can be solved in FPT time f(k)⋅nO(1)f(k) \cdot n^{O(1)}, where kk denotes the size of FF, and nn denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a combination of spectral, geometric, combinatorial and group-theoretic tools.

作者备注:18 pages; second version adds missing attribution of earlier results and improves the write-up

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-18 19:29 · 最新观测版本

FPT Isomorphism Test for $F$-Free Tournaments

We show that isomorphism of FF-free tournaments can be solved in FPT time f(k)⋅nO(1)f(k) \cdot n^{O(1)}, where kk denotes the size of FF, and nn denotes the size of the input tournaments. Our result extends on a previous FPT isomorphism test for tournaments of bounded twin-width [Grohe, Neuen 2024], as well as XP isomorphism tests parameterized by the VC dimension or the chromatic number [Raßmann, Schweitzer 2026]. It also implies that every non-trivial hereditary class of tournaments admits a polynomial-time isomorphism test. Our algorithm builds on a combination of spectral, geometric, combinatorial and group-theoretic tools.

查看此版本解读 →查看此版本原文 ↗