{"id":"arxiv/2602.09576","url":"https://arxiv.org/abs/2602.09576","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"On the complexity of Sandwich Problems for $M$-partitions","domain":"cs.CC","source":"arxiv","authors":["Alexey Barsukov","Santiago Guzmán-Pro"],"reviews":0,"subject":"cs.CC","summary":"We present a structural classification of constraint satisfaction problems (CSP) described by reflexive complete $2$-edge-coloured graphs. In particular, this classification extends the structural dichotomy for graph homomorphism problems known as the Hell--Nešetřil theorem (1990). Our classification is also efficient: we can check in polynomial time whether the CSP of a reflexive complete $2$-edge-coloured graph is in P or NP-complete, whereas for arbitrary $2$-edge-coloured graphs, this task is NP-complete. We then apply our main result in the context of matrix partition problems and…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-10","reactions":{}}