2 papers
cs.CC2023
On guarded extensions of MMSNP
Alexey Barsukov, Florent R. Madelaine
Feder and Vardi showed that the class Monotone Monadic SNP without inequality (MMSNP) has a P vs NP-complete dichotomy if and only if such a dichotomy holds for finite-domain Const…
cs.CC2021
Generalisations of Matrix Partitions : Complexity and Obstructions
Alexey Barsukov, Mamadou Moustapha Kanté
A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or (both an arc and a non-arc). In a series of papers, Hell and co-authors pr…