Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy
V. Arvind, Piyush P. Kurur, T. Vijayaraghavan · 2005
In this paper we study the complexity of bounded color multiplicity graph isomorphism BCGI/sub b/: the input is a pair of vertex-colored graphs such that the number of vertices of a given color in an input graph is bounded by b. We show that BCGI/sub b/ is in the #L hierarchy (more precisely, the Mod/sub k/L hierarchy for some constant k depending on b). Combined with the fact that bounded color multiplicity graph isomorphism is logspace many-one hard for every set in the Mod/sub k/L hierarchy for any constant k, we get a tight classification of the problem using logspace-bounded counting classes.