ECCC-Report TR04-121https://eccc.weizmann.ac.il/report/2004/121Comments and Revisions published for TR04-121en-usWed, 22 Dec 2004 16:56:20 +0200
Paper TR04-121
| Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy. |
Vikraman Arvind,
Piyush Kurur,
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2004/121
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.
Wed, 22 Dec 2004 16:56:20 +0200https://eccc.weizmann.ac.il/report/2004/121