TR04-121 Authors: Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

Publication: 22nd December 2004 16:56

Downloads: 3146

Keywords:

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.