Abstract:
In this paper we study the complexity of Bounded Color Multiplicity Graph Isomorphism (BCGI): 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 is in the #L hierarchy (more precisely, the Mod_kL 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_kL hierarchy for any constant $k$, we get a tight classification of the problem using logspace-bounded counting classes.