The subdirectly irreducible algebras in the variety generated by graph algebras (Q2481704)

Let \(G=(V,E)\) be a directed graph without multiple edges and with loops allowed and \(0\not\in V\). Then the groupoid \((V\cup\{0\},\cdot)\) where \(xy:=x\) if \((x,y)\in E\) and \(xy:=0\) otherwise is called the graph algebra of \(G\). Let \({\mathcal V}\) denote the variety generated by all graph algebras. It is shown that every non-trivial subdirectly irreducible algebra belonging to \({\mathcal V}\) is either a two-element left zero semigroup or a graph algebra itself. A characterization of all subdirectly irreducible algebras belonging to \({\mathcal V}\) is given. From this, an example of a groupoid generating a variety with \(\text{NP}\)-complete membership problem is derived.