The smallest hard trees
DOI10.1007/s10601-023-09341-8zbMath1521.05019arXiv2205.07528OpenAlexW4360948927MaRDI QIDQ6073305
Jakub Bulín, Florian Starke, Manuel Bodirsky, Michael Wernthaler
Publication date: 15 September 2023
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2205.07528
treecomputational complexitypolymorphismgraph homomorphismconstraint satisfaction problemDatalogarc consistencylinear Datalogbounded pathwidth dualitysymmetric linear Datalog
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- Maltsev digraphs have a majority polymorphism
- The core of a graph
- When is a random graph projective?
- Conservative constraint satisfaction re-revisited
- CSP duality and trees of bounded pathwidth
- Existence theorems for weakly symmetric operations
- Universal algebra and hardness results for constraint satisfaction problems
- On the complexity of H-coloring
- On generating all maximal independent sets
- Polynomial graph-colorings
- Consistency in networks of relations
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- The wonderland of reflections
- Implementing a test for tractability
- Principles and practice of constraint programming -- CP '96. Second international conference, CP '96, Cambridge, MA, USA, August 19--22, 1996. Proceedings
- Complexity of tree homomorphisms
- Characterizations of several Maltsev conditions.
- Majority constraints have bounded pathwidth duality
- Practical graph isomorphism. II.
- Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
- CSP for binary conservative relational structures
- Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
- CSP DICHOTOMY FOR SPECIAL POLYADS
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- A Model-Theoretic View on Qualitative Constraint Reasoning
- Near Unanimity Constraints Have Bounded Pathwidth Duality
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Complexity of Infinite-Domain Constraint Satisfaction
- CSP dichotomy for special triads
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- A finer reduction of constraint problems to digraphs
- Directed st-Connectivity Is Not Expressible in Symmetric Datalog
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- The structure of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- Weak consistency notions for all the CSPs of bounded width
- Duality and Polynomial Testing of Tree Homomorphisms
- Finitely Related Algebras In Congruence Distributive Varieties Have Near Unanimity Terms
- Asking the Metaquestions in Constraint Tractability
- The shape of congruence lattices
- A Proof of the CSP Dichotomy Conjecture
- Constraint Satisfaction Problems of Bounded Width
- Linear Datalog and Bounded Path Duality of Relational Structures
- Classifying the Complexity of Constraints Using Finite Algebras
- A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
This page was built for publication: The smallest hard trees
