ARArash Rafiey

Arash Rafiey

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Arash Rafiey has a total of 37 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Interval H-graphs : Recognition and forbidden obstructions

    by Haiko Müller, Arash Rafiey

    We introduce the class of interval $H$-graphs, which is the generalization of interval graphs, particularly interval bigraphs. For a fixed graph $H$ with vertices $a_1,a_2,\dots,a_k$, we say that an input graph $G$ with given partition $V_1,\dots,V_k$ of its vertices is an interval $H$-graph if each vertex $v \in G$ can be represented by an interval $I_v$ from a real line so that $u \in V_i$ and $v \in V_j$ are adjacent if and only if $a_ia_j$ is an edge of $H$ and intervals $I_u$ and $I_v$ intersect. $G$ is called interval $k$-graph if $H$ is a complete graph on $k$ vertices. and interval bigraph when $k=2$. We study the ordering characterization and forbidden obstructions of interval $k$-graphs and present a polynomial-time recognition algorithm for them. Additionally, we discuss how this algorithm can be extended to recognize general interval $H$-graphs. Special cases of interval $k$-graphs, particularly comparability interval $k$-graphs, were previously studied in [2], where the complexity interval $k$-graph recognition was posed as an open problem.


  • Min Orderings and List Homomorphism Dichotomies for Graphs and Signed Graphs

    by Jan Bok, Richard C. Brewster, Pavol Hell, Nikola Jedličková, Arash Rafiey

  • Vertex Ordering with Precedence Constraints

    by Jeff Kinne, Akbar Rafiey, Arash Rafiey, Mohammad Sorkhpar


  • Open Access

    Toward a Dichotomy for Approximation of $H$-coloring

    by Akbar Rafiey, Arash Rafiey, Thiago Santos

    Given two (di)graphs G, H and a cost function $c:V(G)\times V(H) \to \mathbb{Q}_{\geq 0}\cup\{+\infty\}$, in the minimum cost homomorphism problem, MinHOM(H), goal is finding a homomorphism $f:V(G)\to V(H)$ (a.k.a H-coloring) that minimizes $\sum\limits_{v\in V(G)}c(v,f(v))$. The complexity of exact minimization of this problem is well understood [34], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. For digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph. For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a conservative semi-lattice polymorphism or min-ordering), and k-arc digraphs (digraphs with an extended min-ordering). Specifically, we show that: 1. Dichotomy for Graphs: MinHOM(H) has a $2|V(H)|$-approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a bi-arc graph), otherwise, it is inapproximable; 2. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a bi-arc digraph; 3. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a k-arc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of H.

  • Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs

    by Jan Bok, Richard C. Brewster, Pavol Hell, Nikola Jedličková, Arash Rafiey


  • 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.