Generalisations of matrix partitions: complexity and obstructions

DOI10.1016/J.TCS.2024.114652MaRDI QIDQ6564025zbMATH OpenFDO

Authors Alexey Barsukov, Mamadou Moustapha Kanté

Publication date 28 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114652

zbMATH Keywords

complexityCSPdichotomy theoremmatrix partition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• A closed set of normal orthogonal functions.
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• A finer reduction of constraint problems to digraphs
• A proof of the CSP dichotomy conjecture
• Classifying the Complexity of Constraints Using Finite Algebras
• Colourings, homomorphisms, and partitions of transitive digraphs
• Dualities in full homomorphisms
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Expander graphs and their applications
• Graph complexity
• Graph partitions with prescribed patterns
• Graph structure and monadic second-order logic. A language-theoretic approach
• List Partitions
• Matrix partitions of split graphs
• Matrix partitions with finitely many obstructions
• On digraph coloring problems and treewidth duality
• On realizations of point determining graphs, and obstructions to full homomorphisms
• On the Structure of Polynomial Time Reducibility
• On the algebraic structure of combinatorial problems
• On the complexity of H-coloring
• On the density of trigraph homomorphisms
• QCSP Monsters and the Demise of the Chen Conjecture
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of conservative valued CSPs
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of locally injective homomorphisms
• The complexity of satisfiability problems
• The complexity of surjective homomorphism problems-a survey
• The dichotomy of list homomorphisms for digraphs
• The number of submatrices of a given type in a Hadamard matrix and related results

Cited in

(1)

• On guarded extensions of MMSNP

This page was built for publication: Generalisations of matrix partitions: complexity and obstructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6564025)