Parameterised complexity of graph homomorphism to odd cycles
Version 1 / Nov 19, 2026 / CC BY 4.0
Abstract
A nonbipartite graph has an odd-cycle core precisely when it maps to its shortest odd cycle. Core recognition and homomorphism to an input odd cycle are both XNLP-complete for the width of a supplied path decomposition, XALP-complete for the width of a supplied tree decomposition, and W[SAT]-hard and in W[P] for feedback vertex number. Hardness persists on connected, 2-degenerate -vertex sources of girth for any fixed . Our reduction encodes lists by cycles sharing an edge. On inputs with an edge it increases treewidth and feedback vertex number by exactly two. Lean 4 checks this structural transfer. For feedback edge number , we compute the exact circular chromatic number in time up to polynomial factors, which gives the same upper bound for both decision problems.
Provenance statement
Tools used
- Anthropic
- Claude CodeVersion Claude Opus 5.5
- OpenAI
- CodexVersion GPT-6-Astra
- Lean
- LeanVersion 4
References
- K. A. Abrahamson, R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic 73(3):235--276, 1995. doi:10.1016/0168-0072(94)00034-Z (https://doi.org/10.1016/0168-0072(94)00034-Z).DOI
- Antoine Amarilli. Complexity of the homomorphism problem parameterized by treewidth. Theoretical Computer Science Stack Exchange , question 34877, June 2, 2016, with a comment on workshop reductions, May 30, 2025 (https://cstheory.stackexchange.com/questions/34877/#comment124806_34877). https://cstheory.stackexchange.com/q/34877.link
- Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk and Michał Pilipczuk. On the complexity of problems on tree-structured graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) , LIPIcs, vol. 249, pp. 6:1--6:17. Schloss Dagstuhl, 2022. doi:10.4230/LIPIcs.IPEC.2022.6 (https://doi.org/10.4230/LIPIcs.IPEC.2022.6).DOI
- Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and Céline Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. Information and Computation 300:105195, 2024. doi:10.1016/j.ic.2024.105195 (https://doi.org/10.1016/j.ic.2024.105195).DOI
- Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , LIPIcs, vol. 261, pp. 27:1--27:20. Schloss Dagstuhl, 2023. doi:10.4230/LIPIcs.ICALP.2023.27 (https://doi.org/10.4230/LIPIcs.ICALP.2023.27).DOI
- Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized complexity of Binary CSP: vertex cover, treedepth, and related parameters. Full version, arXiv:2208.12543v5 (https://arxiv.org/abs/2208.12543v5), 2023.arXiv
- Clément Carbonnel. Faster algorithms for graph homomorphism via tractable constraint satisfaction. arXiv:2602.23000v2 (https://arxiv.org/abs/2602.23000v2), 2026.arXiv
- Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh. Parameterized Algorithms . Springer, 2015. doi:10.1007/978-3-319-21275-3 (https://doi.org/10.1007/978-3-319-21275-3).DOI
- Jason Davies. Odd-cycle homomorphism: Lean formalisation and executable checks. Software repository, 2026. Version 848545a (https://github.com/jasondavies/odd-cycle-homomorphism/tree/848545ac03da8691fdd511e29b3e247e446fb523). https://github.com/jasondavies/odd-cycle-homomorphism.link
- Béla Bollobás and Endre Szemerédi. Girth of sparse graphs. Journal of Graph Theory 39(3):194--200, 2002. doi:10.1002/jgt.10023 (https://doi.org/10.1002/jgt.10023).DOI
Show all 21 referencesShow fewer references
- Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction -- CADE 28 , LNCS, vol. 12699, pp. 625--635. Springer, 2021. doi:10.1007/978-3-030-79876-5_37 (https://doi.org/10.1007/978-3-030-79876-5_37).DOI
- Jörg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. Springer, 2006. doi:10.1007/3-540-29953-X (https://doi.org/10.1007/3-540-29953-X).DOI
- A. M. H. Gerards. Homomorphisms of graphs into odd cycles. Journal of Graph Theory 12(1):73--83, 1988. doi:10.1002/jgt.3190120108 (https://doi.org/10.1002/jgt.3190120108).DOI
- Hossein Hajiabolhassan and Ali Taherkhani. On the circular chromatic number of graph powers. Journal of Graph Theory 75(1):48--58, 2014. doi:10.1002/jgt.21722 (https://doi.org/10.1002/jgt.21722).DOI
- A. Kostochka, J. Nešetřil and P. Smolíková. Colorings and homomorphisms of degenerate and bounded degree graphs. Discrete Mathematics 233:257--276, 2001. doi:10.1016/S0012-365X(00)00245-4 (https://doi.org/10.1016/S0012-365X(00)00245-4).DOI
- Jason Davies. Homomorphisms to long odd cycles in time exponential in the order-to-length ratio. Companion manuscript, 2026. Distributed alongside this paper as long-odd-cycles.pdf .
- The mathlib Community. The Lean mathematical library. In Certified Programs and Proofs (CPP 2020) , pp. 367--381. ACM, 2020. doi:10.1145/3372885.3373824 (https://doi.org/10.1145/3372885.3373824).DOI
- Karolina Okrasa and Paweł Rzążewski. Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs. SIAM Journal on Computing 50(2):487--508, 2021. doi:10.1137/20M1320146 (https://doi.org/10.1137/20M1320146). Preprint version: arXiv:1906.08371v3 (https://arxiv.org/abs/1906.08371v3), 2020.arXivDOI
- Marta Piecyk and Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) , LIPIcs, vol. 187, pp. 56:1--56:17. Schloss Dagstuhl, 2021. doi:10.4230/LIPIcs.STACS.2021.56 (https://doi.org/10.4230/LIPIcs.STACS.2021.56).DOI
- Andrew Vince. Star chromatic number. Journal of Graph Theory 12(4):551--559, 1988. doi:10.1002/jgt.3190120411 (https://doi.org/10.1002/jgt.3190120411).DOI
- Xuding Zhu. Circular chromatic number: a survey. Discrete Mathematics 229(1--3):371--410, 2001. doi:10.1016/S0012-365X(00)00217-X (https://doi.org/10.1016/S0012-365X(00)00217-X).DOI
Version history
- v1 · 15 pagesSubmitted by Jason DaviesInitial depositCurrentNov 19, 2026