AMAshwin Murali

Ashwin Murali

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Ashwin Murali has a total of 3 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Digraph homomorphism problem and weak near unanimity polymorphism

    by Tomas Feder, Jeff Kinne, Ashwin Murali, Arash Rafiey

    We consider the problem of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$. We show that if $H$ admits a weak near unanimity polymorphism $\phi$ then deciding whether $G$ admits a homomorphism to $H$ (HOM($H$)) is polynomial-time solvable. This gives proof of the dichotomy conjecture (now dichotomy theorem) by Feder and Vardi. Our approach is combinatorial, and it is simpler than the two algorithms found by Bulatov and Zhuk. We have implemented our algorithm and show some experimental results. We use our algorithm together with the recent result [38] for recognition of Maltsev polymorphisms and decide in polynomial time if a given relational structure $\mathcal{R}$ admits a weak near unanimity polymorphism.

  • Open Access

    Digraphs Homomorphism Problems with Maltsev Condition

    by Jeff Kinne, Ashwin Murali, Arash Rafiey

    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.

  • Open Access

    Dichotomy for Digraph Homomorphism Problems

    by Tomás Feder, Jeff Kinne, Ashwin Murali, Arash Rafiey

    We consider the problem of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$. We show that if $H$ admits a weak-near-unanimity polymorphism $\phi$ then deciding whether $G$ admits a homomorphism to $H$ (HOM($H$)) is polynomial time solvable? This gives a proof of the dichotomy conjecture (now dichotomy theorem) by Feder and Vardi [29]. Our approach is combinatorial, and it is simpler than the two algorithms found by Bulatov [9] and Zhuk [46] in 2017. We have implemented our algorithm and show some experimental results.