Parameterised complexity of graph homomorphism to odd cycles

Contributed by Jason Davies ↗

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 NN-vertex sources of girth Ω(N1−ε)\Omega(N^{1-\varepsilon}) for any fixed 0<ε<10<\varepsilon<1. 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 rr, we compute the exact circular chromatic number in 2O(r)2^{O(r)} time up to polynomial factors, which gives the same upper bound for both decision problems.

Provenance statement

Research direction, editorial choices and responsibility are the author's. AI agents (OpenAI Codex and AI-assisted review sessions) assisted with mathematical exploration, Lean proof development, executable checks, manuscript drafting and review; revisions addressed the agents' concrete findings. The structural transfer theorem is machine-checked in Lean 4.35.0 with mathlib v4.35.0, with no sorries and only the axioms propext, Classical.choice and Quot.sound. The circular-colouring algorithm, girth amplification, encodings and running-time analyses are proved in the manuscript but are not formalised. 841 finite instances were also checked in Python. Exact model identifiers and costs were not comprehensively recorded.

Tools used

Anthropic
Claude CodeVersion Claude Opus 5.5
OpenAI
CodexVersion GPT-6-Astra
Lean
LeanVersion 4

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. Clément Carbonnel. Faster algorithms for graph homomorphism via tractable constraint satisfaction. arXiv:2602.23000v2 (https://arxiv.org/abs/2602.23000v2), 2026.arXiv
  8. 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
  9. 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
  10. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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 .
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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

  1. v1 · 15 pagesSubmitted by Jason DaviesInitial depositCurrentNov 19, 2026