5 papers
Cut-homotopies and the complexity of edge-coloring problems
Alexey Barsukov, Roman Feller, Maximilian Hadek +1
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 s…
Towards infinite PCSP: a dichotomy for monochromatic cliques
Demian Banakh, Alexey Barsukov, Tamio-Vesa Nakajima
The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs)…
Edge-coloring problems with forbidden patterns and planted colors
Alexey Barsukov, Antoine Mottet, Davide Perinti
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…
The Golden Path to Guarded Monotone Strict NP
Alexey Barsukov, Michael Pinsker, Jakub Rydval
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment and…
On the complexity of Sandwich Problems for -partitions
Alexey Barsukov, Santiago Guzmán-Pro
We present a structural classification of constraint satisfaction problems (CSP) described by reflexive complete -edge-coloured graphs. In particular, this classification extend…