The subdirectly irreducible algebras in the variety generated by graph algebras

We show that every non-trivial subdirectly irreducible algebra in the variety generated by graph algebras is either a two-element left zero semigroup or a graph algebra itself. We characterize all the subdirectly irreducible algebras in this variety. From this we derive an example of a groupoid (graph algebra) that generates a variety with NP-complete membership problem. This is an improvement over the result of Z. Székely who constructed an algebra with similar properties in the signature of two binary operations. The second author was supported by OTKA grants no. T043671, NK67867, K67870 and by NKTH (National Office for Research and Technology, Hungary).