Cut-homotopies and the complexity of edge-coloring problems
2026-07-10 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors explore how hard it is to decide if you can color a graph's edges without creating certain colored cliques (small fully connected subgraphs) from a set of forbidden patterns. They prove that these coloring problems are essentially the same difficulty as well-known logical problems called Constraint Satisfaction Problems (CSPs). This means each problem is either easy to solve quickly or as hard as the hardest problems in NP. Their key work involves connecting CSPs to these coloring problems using ideas from Ramsey theory and a new concept called cut-homotopy.
Graph edge-coloringEdge-colored cliqueConstraint Satisfaction Problem (CSP)Computational complexityP vs. NP-completeRamsey theoryCut-homotopyPolynomial-time reductionGraph theoryHomotopy theory
Authors
Alexey Barsukov, Roman Feller, Maximilian Hadek, Davide Perinti
Abstract
We study the computational complexity of problems that ask if a given graph admits an edge-coloring that does not contain an edge-colored clique from some fixed finite family. We show that every such problem is poly-time equivalent to a Constraint Satisfaction Problem, yielding a P vs. NP-complete dichotomy. Our main contribution lies in the reduction from the CSP to the coloring problem where we apply methods from Ramsey theory and a novel notion of cut-homotopy.