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)

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

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)