pith. sign in

arxiv: 2507.19000 · v2 · submitted 2025-07-25 · 💻 cs.CC · cs.DM

Edge-coloring problems with forbidden patterns and planted colors

Alexey Barsukov , Antoine Mottet , Davide Perinti This is my paper

Pith reviewed 2026-05-19 03:40 UTC · model grok-4.3

classification 💻 cs.CC cs.DM
keywords edge-coloringforbidden patternsprecoloringconstraint satisfactioncomplexity dichotomyRamsey theory
0
0 comments X

The pith

For forbidden families of odd cycles and cliques, edge-coloring problems with forbidden patterns reduce to finite constraint satisfaction problems and thus fall into P or NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper settles a classification question for a class of edge-coloring decision problems that ask whether a graph admits an edge coloring avoiding a homomorphism from any member of a fixed forbidden family. For families built from odd cycles and cliques, the unrestricted problem is shown to be polynomial-time equivalent to its precolored version. The precolored version is then shown to be polynomial-time equivalent to a finite constraint satisfaction problem. Known dichotomy theorems for finite constraint satisfaction problems therefore supply a complete P versus NP-complete classification for the original problems.

Core claim

For forbidden families consisting of odd cycles and cliques, the edge-coloring problem with forbidden patterns is polynomial-time equivalent to its precolored version, and the precolored version is polynomial-time equivalent to a finite constraint satisfaction problem.

What carries the argument

Two-stage reduction that first applies infinite constraint satisfaction techniques together with finite Ramsey theory to equate the unrestricted edge-coloring problem to its precolored version, then reduces the precolored version to a finite constraint satisfaction problem.

If this is right

  • The problems receive a complete complexity classification inherited from the dichotomy for finite constraint satisfaction problems.
  • No problems in this class can have intermediate complexity between P and NP-complete.
  • The classification applies uniformly to all input graphs once the forbidden family is fixed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction strategy could be tested on other small forbidden families to see whether the equivalence to finite constraint satisfaction continues to hold.
  • If the method generalizes, similar classifications might become available for homomorphism problems on other relational structures beyond edge colorings.
  • One could look for concrete small families where the Ramsey-theoretic step simplifies to an elementary combinatorial argument.

Load-bearing premise

The chosen combination of infinite constraint satisfaction methods and finite Ramsey theory is enough to establish polynomial-time equivalence between the edge-coloring problem and its precolored version for these particular families.

What would settle it

An explicit family of odd cycles and cliques for which the edge-coloring problem lies outside both P and NP-complete, or for which the claimed polynomial-time reduction to a finite constraint satisfaction problem does not hold.

read the original abstract

Edge-coloring problems with forbidden patterns are decision problems asking to find an edge-coloring of the input graph which avoids a homomorphism from a fixed forbidden family of edge-colored graphs. In the precolored version of these problems, some of the edges of the input graph are already colored, and the goal is to find an extension of this coloring which omits a homomorphism from a forbidden graph. The existence of a complexity classification for such problems is an open question of Bienvenu, ten Cate, Lutz, and Wolter (ACM TODS'14) and we answer it for certain forbidden families consisting of odd cycles and cliques. The proof consists of two main stages. First, we combine the techniques from infinite constraint satisfaction and finite Ramsey theory in order to show that the edge-coloring problem is poly-time equivalent to its precolored version. After that, we show that the precolored version is poly-time equivalent to a finite constraint satisfaction problem, which has a P vs.\ NP-complete dichotomy by the seminal results of Bulatov (FOCS'17) and Zhuk (FOCS'17).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper resolves an open question from Bienvenu et al. (ACM TODS'14) on the complexity of edge-coloring problems with forbidden patterns, for the specific case of forbidden families consisting of odd cycles and cliques. It proceeds in two stages: first establishing polynomial-time equivalence between the unrestricted edge-coloring problem and its precolored version by combining infinite-CSP techniques with finite Ramsey theory; second, reducing the precolored version to a finite CSP and invoking the Bulatov-Zhuk dichotomy to obtain a P vs. NP-complete classification.

Significance. If the reductions are polynomial-time and the equivalences hold, the result supplies the first complexity classification for these forbidden-pattern edge-coloring problems, illustrating a productive fusion of Ramsey theory with infinite and finite CSP methods. The explicit appeal to the Bulatov-Zhuk theorem is a strength, as it yields a clean dichotomy once the reductions are established.

major comments (2)
  1. [§3] §3 (first stage of the proof): the claimed polynomial-time equivalence between the edge-coloring problem and its precolored version rests on an application of finite Ramsey theory. The abstract asserts that this yields a poly-time reduction, yet the manuscript must explicitly verify that Ramsey witnesses for the chosen odd-cycle families (e.g., C_5 and larger) can be found in polynomial time and produce a precolored instance whose size is polynomial in the input; mere existence of monochromatic substructures does not guarantee an algorithmic, polynomial-size reduction.
  2. [§4] §4 (reduction to finite CSP): the second-stage equivalence must be shown to preserve the complexity classification without introducing new parameters that escape the Bulatov-Zhuk dichotomy; if the finite CSP template depends on the specific forbidden family in a way that requires case-by-case verification, this should be stated explicitly rather than left implicit.
minor comments (2)
  1. [Abstract] The abstract and introduction should include a brief statement of the precise forbidden families (which odd cycles and which cliques) to make the scope immediately clear.
  2. [§2] Notation for homomorphisms and precolorings is introduced without a dedicated preliminary section; a short table or paragraph defining the key symbols would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying points that require additional clarification. We address each major comment below and indicate the revisions that will be incorporated in the next version.

read point-by-point responses

  1. Referee: [§3] §3 (first stage of the proof): the claimed polynomial-time equivalence between the edge-coloring problem and its precolored version rests on an application of finite Ramsey theory. The abstract asserts that this yields a poly-time reduction, yet the manuscript must explicitly verify that Ramsey witnesses for the chosen odd-cycle families (e.g., C_5 and larger) can be found in polynomial time and produce a precolored instance whose size is polynomial in the input; mere existence of monochromatic substructures does not guarantee an algorithmic, polynomial-size reduction.

    Authors: We agree that the current presentation relies primarily on the existence of Ramsey witnesses and does not supply an explicit algorithmic argument. For the fixed families consisting of odd cycles and cliques, the relevant Ramsey numbers are constants (independent of the input graph), and standard constructive proofs of Ramsey’s theorem for these small forbidden structures admit polynomial-time algorithms that produce monochromatic subgraphs of size bounded by a constant. Consequently the precolored instance can be built in polynomial time and remains polynomial in size. We will add a dedicated paragraph in §3 that spells out this algorithmic construction, cites the relevant constant-size Ramsey bounds, and proves the polynomial-time bound on the reduction. revision: yes

  2. Referee: [§4] §4 (reduction to finite CSP): the second-stage equivalence must be shown to preserve the complexity classification without introducing new parameters that escape the Bulatov-Zhuk dichotomy; if the finite CSP template depends on the specific forbidden family in a way that requires case-by-case verification, this should be stated explicitly rather than left implicit.

    Authors: The finite CSP template is obtained by a uniform, polynomial-time construction from the fixed forbidden family; once the family is chosen, the template is a fixed finite relational structure. The Bulatov–Zhuk dichotomy therefore applies directly to every such template without introducing variable parameters or requiring separate case analysis. We will revise the opening paragraph of §4 to state explicitly that the template is fixed for each forbidden family and that the dichotomy classification is inherited verbatim via the polynomial-time equivalence. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation chains to external theorems

full rationale

The paper establishes poly-time equivalence between the edge-coloring problem and its precolored version by combining infinite-CSP techniques with finite Ramsey theory, then reduces the precolored version to a finite CSP whose dichotomy follows from the independent Bulatov-Zhuk theorems. These steps invoke externally verified results rather than internal definitions, fitted parameters, or self-citation chains that presuppose the target equivalences. No load-bearing step reduces by construction to quantities defined inside the paper.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Bulatov-Zhuk dichotomy theorem for finite CSPs and on the applicability of infinite-CSP and Ramsey-theoretic tools to the chosen families; no free parameters or new entities are introduced.

axioms (1)
  • standard math The Bulatov-Zhuk dichotomy theorem holds for finite-domain constraint satisfaction problems.
    Invoked after the reduction to conclude that the precolored problem is either in P or NP-complete.

pith-pipeline@v0.9.0 · 5723 in / 1368 out tokens · 33825 ms · 2026-05-19T03:40:52.298579+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Containment for Guarded Monotone Strict NP

    Alexey Barsukov, Michael Pinsker, and Jakub Rydval. Containment for Guarded Monotone Strict NP . In Keren Censor-Hillel, Fabrizio Grandoni, Jo\" e l Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , volume 334 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 140...

    work page doi:10.4230/lipics.icalp.2025.140 2025

  2. [2]

    Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem

    Libor Barto and Marcin Kozik. Absorbing subalgebras, cyclic terms, and the constraint satisfaction problem. Log. Methods Comput. Sci. , 8(1), 2012. https://doi.org/10.2168/LMCS-8(1:7)2012 doi:10.2168/LMCS-8(1:7)2012

    work page doi:10.2168/lmcs-8(1:7)2012 2012

  3. [3]

    Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP

    Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, and Frank Wolter. Ontology-Based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP . ACM Trans. Database Syst. , 39(4):33:1--33:44, 2014. https://doi.org/10.1145/2661643 doi:10.1145/2661643

    work page doi:10.1145/2661643 2014

  4. [4]

    Generalized completion problems with forbidden tournaments

    Zeno Bitter and Antoine Mottet. Generalized completion problems with forbidden tournaments. In Rastislav Kr \' a lovi c and Anton \' n Ku c era, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia , volume 306 of LIPIcs , pages 28:1--28:17. Schloss Dagstuhl - Leibniz-Ze...

    work page doi:10.4230/lipics.mfcs.2024.28 2024

  5. [5]

    Complexity of Infinite-Domain Constraint Satisfaction

    Manuel Bodirsky. Complexity of Infinite-Domain Constraint Satisfaction . Lecture Notes in Logic. Cambridge University Press, 2021. Postprint available online: https://wwwpub.zih.tu-dresden.de/ bodirsky/Book.pdf. https://doi.org/10.1017/9781107337534 doi:10.1017/9781107337534

    work page doi:10.1017/9781107337534 2021

  6. [6]

    Forbidden tournaments and the orientation completion problem

    Manuel Bodirsky and Santiago Guzm \' a n - Pro. Forbidden tournaments and the orientation completion problem. SIAM J. Discret. Math. , 39(1):170--205, 2025. URL: https://doi.org/10.1137/23m1604849, https://doi.org/10.1137/23M1604849 doi:10.1137/23M1604849

    work page doi:10.1137/23m1604849 2025

  7. [7]

    ASNP: A tame fragment of existential second-order logic

    Manuel Bodirsky, Simon Kn \" a uer, and Florian Starke. ASNP: A tame fragment of existential second-order logic. In CiE 2020, Proceedings , volume 12098 of Lecture Notes in Computer Science , pages 149--162. Springer, 2020. https://doi.org/10.1007/978-3-030-51466-2\_13 doi:10.1007/978-3-030-51466-2\_13

    work page doi:10.1007/978-3-030-51466-2 2020

  8. [8]

    Madelaine, and Antoine Mottet

    Manuel Bodirsky, Florent R. Madelaine, and Antoine Mottet. A proof of the algebraic tractability conjecture for monotone monadic SNP . SIAM J. Comput. , 50(4):1359--1409, 2021. https://doi.org/10.1137/19M128466X doi:10.1137/19M128466X

    work page doi:10.1137/19m128466x 2021

  9. [9]

    Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction

    Manuel Bodirsky and Antoine Mottet. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016 , pages 623-...

    work page doi:10.1145/2933575.2934515 2016

  10. [10]

    Canonical functions: a proof via topological dynamics

    Manuel Bodirsky and Michael Pinsker. Canonical functions: a proof via topological dynamics. Contributions Discret. Math. , 16(2):36--45, 2021. https://doi.org/10.11575/cdm.v16i2.71724 doi:10.11575/cdm.v16i2.71724

    work page doi:10.11575/cdm.v16i2.71724 2021

  11. [11]

    Decidability of Definability

    Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. Decidability of Definability . J. Symb. Log. , 78(4):1036--1054, 2013. https://doi.org/10.2178/jsl.7804020 doi:10.2178/jsl.7804020

    work page doi:10.2178/jsl.7804020 2013

  12. [12]

    On the use of senders for asymmetric tuples of cliques in Ramsey theory

    Simona Boyadzhiyska and Thomas Lesgourgues. On the use of senders for asymmetric tuples of cliques in Ramsey theory. Journal of Combinatorial Theory, Series B , 169:63--95, November 2024. URL: https://linkinghub.elsevier.com/retrieve/pii/S0095895624000455, https://doi.org/10.1016/j.jctb.2024.05.006 doi:10.1016/j.jctb.2024.05.006

    work page doi:10.1016/j.jctb.2024.05.006 2024

  13. [13]

    Andrei A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs . In C. Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pages 319--330. IEEE Computer Society, 2017. https://doi.org/10.1109/FOCS.2017.37 doi:10.1109/FOCS.2017.37

    work page doi:10.1109/focs.2017.37 2017

  14. [14]

    Stefan A. Burr. On the Computational Complexity of Ramsey — Type Problems . In Jaroslav Nešetřil and Vojtěch Rödl, editors, Mathematics of Ramsey Theory , volume 5, pages 46--52. Springer Berlin Heidelberg, Berlin, Heidelberg, 1990. Series Title: Algorithms and Combinatorics. URL: http://link.springer.com/10.1007/978-3-642-72905-8_5, https://doi.org/10.10...

    work page doi:10.1007/978-3-642-72905-8_5 1990

  15. [15]

    Burr, Paul Erd o s, and L \'a szl \'o Lov \'a sz

    Stefan A. Burr, Paul Erd o s, and L \'a szl \'o Lov \'a sz. On graphs of R amsey type. 1976. URL: https://api.semanticscholar.org/CorpusID:17474857

    work page 1976

  16. [16]

    Burr, Jaroslav Ne s et r il, and Vojt e ch R \" o dl

    Stefan A. Burr, Jaroslav Ne s et r il, and Vojt e ch R \" o dl. On the use of senders in generalized ramsey theory for graphs. Discrete Mathematics , 54(1):1--13, March 1985. URL: https://www.sciencedirect.com/science/article/pii/0012365X85900573, https://doi.org/10.1016/0012-365X(85)90057-3 doi:10.1016/0012-365X(85)90057-3

    work page doi:10.1016/0012-365x(85)90057-3 1985

  17. [17]

    Tom \' a s Feder and Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory . SIAM J. Comput. , 28(1):57--104, 1998. https://doi.org/10.1137/S0097539794266766 doi:10.1137/S0097539794266766

    work page doi:10.1137/s0097539794266766 1998

  18. [18]

    An algebraic proof of the graph orientation problem dichotomy for forbidden tournaments

    Roman Feller and Michael Pinsker. An algebraic proof of the graph orientation problem dichotomy for forbidden tournaments. CoRR , abs/2405.20263, 2024. URL: https://doi.org/10.48550/arXiv.2405.20263, http://arxiv.org/abs/2405.20263 arXiv:2405.20263 , https://doi.org/10.48550/ARXIV.2405.20263 doi:10.48550/ARXIV.2405.20263

    work page doi:10.48550/arxiv.2405.20263 2024

  19. [19]

    Generalised dualities and maximal finite antichains in the homomorphism order of relational structures

    Jan Foniok, Jaroslav Ne s et r il, and Claude Tardif. Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. Eur. J. Comb. , 29(4):881--899, 2008. URL: https://doi.org/10.1016/j.ejc.2007.11.017, https://doi.org/10.1016/J.EJC.2007.11.017 doi:10.1016/J.EJC.2007.11.017

    work page doi:10.1016/j.ejc.2007.11.017 2008

  20. [20]

    A Shorter Model Theory

    Wilfrid Hodges. A Shorter Model Theory . Cambridge University Press, USA, 1997

    work page 1997

  21. [21]

    All those R amsey classes ( R amsey classes with closures and forbidden homomorphisms)

    Jan Hubi c ka and Jaroslav Ne s et r il. All those R amsey classes ( R amsey classes with closures and forbidden homomorphisms) . Adv. Math. , 356:106791, 2019. https://doi.org/10.1016/j.aim.2019.106791 doi:10.1016/j.aim.2019.106791

    work page doi:10.1016/j.aim.2019.106791 2019

  22. [22]

    Universal structures with forbidden homomorphisms

    Jan Hubi c ka and Jaroslav Ne s et r il. Universal structures with forbidden homomorphisms. In sa Hirvonen, Juha Kontinen, Roman Kossak, and Andr \' e s Villaveces, editors, Logic Without Borders - Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics , volume 5 of Ontos Mathematical Logic , pages 241--264. De Gruyter, 2015...

    work page doi:10.1515/9781614516873.241 2015

  23. [23]

    Homomorphism and embedding universal structures for restricted classes

    Jan Hubi c ka and Jaroslav Ne s et r il. Homomorphism and embedding universal structures for restricted classes. J. Multiple Valued Log. Soft Comput. , 27(2-3):229--253, 2016. URL: http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-27-number-2-3-2016/mvlsc-27-2-3-p-229-253/

    work page 2016

  24. [24]

    Constraints, MMSNP and expander relational structures

    G \' a bor Kun. Constraints, MMSNP and expander relational structures. Combinatorica , 33(3):335--347, 2013. https://doi.org/10.1007/s00493-013-2405-4 doi:10.1007/s00493-013-2405-4

    work page doi:10.1007/s00493-013-2405-4 2013

  25. [25]

    Dichotomy for orderings? CoRR , abs/2504.13268, 2025

    G \' a bor Kun and Jaroslav Ne s et r il. Dichotomy for orderings? CoRR , abs/2504.13268, 2025. URL: https://doi.org/10.48550/arXiv.2504.13268, http://arxiv.org/abs/2504.13268 arXiv:2504.13268 , https://doi.org/10.48550/ARXIV.2504.13268 doi:10.48550/ARXIV.2504.13268

    work page doi:10.48550/arxiv.2504.13268 2025

  26. [26]

    Madelaine

    Florent R. Madelaine. Universal Structures and the logic of Forbidden Patterns . Log. Methods Comput. Sci. , 5, 2009. https://doi.org/10.2168/LMCS-5(2:13)2009 doi:10.2168/LMCS-5(2:13)2009

    work page doi:10.2168/lmcs-5(2:13)2009 2009

  27. [27]

    Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: When symmetries are enough

    Antoine Mottet, Tom \' a s Nagy, Michael Pinsker, and Micha Wrona. Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: When symmetries are enough. SIAM J. Comput. , 53(6):1709--1745, 2024. URL: https://doi.org/10.1137/22m1538934, https://doi.org/10.1137/22M1538934 doi:10.1137/22M1538934

    work page doi:10.1137/22m1538934 2024

  28. [28]

    Cores over R amsey structures

    Antoine Mottet and Michael Pinsker. Cores over R amsey structures. J. Symb. Log. , 86(1):352--361, 2021. URL: https://doi.org/10.1017/jsl.2021.6, https://doi.org/10.1017/JSL.2021.6 doi:10.1017/JSL.2021.6

    work page doi:10.1017/jsl.2021.6 2021

  29. [29]

    Smooth approximations: An algebraic approach to CSP s over finitely bounded homogeneous structures

    Antoine Mottet and Michael Pinsker. Smooth approximations: An algebraic approach to CSP s over finitely bounded homogeneous structures. J. ACM , 71(5):36:1--36:47, 2024. https://doi.org/10.1145/3689207 doi:10.1145/3689207

    work page doi:10.1145/3689207 2024

  30. [30]

    The R amsey property for graphs with forbidden complete subgraphs

    Jaroslav Ne s et r il and Vojt e ch R \" o dl. The R amsey property for graphs with forbidden complete subgraphs. Journal of Combinatorial Theory, Series B , 20(3):243--249, 1976. URL: https://www.sciencedirect.com/science/article/pii/0095895676900150, https://doi.org/https://doi.org/10.1016/0095-8956(76)90015-0 doi:https://doi.org/10.1016/0095-8956(76)90015-0

    work page doi:10.1016/0095-8956(76)90015-0 1976

  31. [31]

    On R amsey minimal graphs

    Vojt e ch R \" o dl and Mark Siggers. On R amsey minimal graphs. SIAM Journal on Discrete Mathematics , 22(2):467--488, 2008. https://doi.org/10.1137/050647116 doi:10.1137/050647116

    work page doi:10.1137/050647116 2008

  32. [32]

    Homomorphism preservation theorems

    Benjamin Rossman. Homomorphism preservation theorems. J. ACM , 55(3):15:1--15:53, 2008. https://doi.org/10.1145/1379759.1379763 doi:10.1145/1379759.1379763

    work page doi:10.1145/1379759.1379763 2008

  33. [33]

    A Proof of the CSP Dichotomy Conjecture

    Dmitriy Zhuk. A Proof of the CSP Dichotomy Conjecture . J. ACM , 67(5):30:1--30:78, 2020. https://doi.org/10.1145/3402029 doi:10.1145/3402029

    work page doi:10.1145/3402029 2020