Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-121 | 7th December 2004 00:00

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

RSS-Feed




TR04-121
Authors: Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan
Publication: 22nd December 2004 16:56
Downloads: 3592
Keywords: 


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.



ISSN 1433-8092 | Imprint