Digraphs Homomorphism Problems with Maltsev Condition
Preprint
Abstract
We consider a generalization of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$, HOM($H$). In this setting, we are given an input digraph $G$ together with a list function from $G$ to $2^H$. The goal is to find a homomorphism from $G$ to $H$ with respect to the lists if one exists. We show that if the list function is a Maltsev polymorphism then deciding whether $G$ admits a homomorphism to $H$ is polynomial time solvable. In our approach, we only use the existence of the Maltsev polymorphism. Furthermore, we show that deciding whether a relational structure $\mathcal{R}$ admits a Maltsev polymorphism is a special case of finding a homormphism from a graph $G$ to a graph $H$ and a list function with a Maltsev polymorphism. Since the existence of Maltsev is not required in our algorithm, we can decide in polynomial time whether the relational structure $\mathcal{R}$ admits Maltsev or not. We also discuss forbidden obstructions for the instances admitting Maltsev list polymorphism. We have implemented our algorithm and tested on instances arising from linear equations, and other types of instances.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- A Dichotomy Theorem for Nonuniform CSPs2017
- Robust algorithms with polynomial loss for near-unanimity CSPs2017
- Testing Assignments to Constraint Satisfaction Problems2016
- Maltsev digraphs have a majority polymorphismEuropean Journal of Combinatorics, 2011
- A strong Mal’cev condition for locally finite varieties omitting the unary typeAlgebra universalis, 2010
- Existence theorems for weakly symmetric operationsAlgebra universalis, 2008
- List homomorphisms of graphs with bounded degreesDiscrete Mathematics, 2007
- A Simple Algorithm for Mal'tsev ConstraintsSIAM Journal on Computing, 2006
- Bi‐arc graphs and the complexity of list homomorphismsJournal of Graph Theory, 2002
- List Homomorphisms and Circular Arc GraphsCombinatorica, 1999