Affiliations: Dept. of Computer Science, University of Colorado at
Boulder Boulder, CO 80309, USA | Institute of Information and Computing Science,
Universiteit Utrecht P.O. Box 80.089, 3508 TB Utrecht, Netherlands. E-mail:
[email protected] | Department of Mathematics, University of Turku
FIN-20014 Turku, Finland. E-mail: [email protected] | Leiden Institute of Advanced Computer Science P.O. Box
9512, 2300 RA Leiden, The Netherlands
Abstract: In the context of graph transformation we look at the operation of
switching, which can be viewed as a method for realizing global transformations
of (group-labelled) graphs through local transformations of the vertices. In case vertices are given an identity, various relatively efficient
algorithms exist for deciding whether a graph can be switched so that it
contains some other graph, the query graph, as an induced subgraph. However,
when considering graphs up to isomorphism, we immediately run into the graph
isomorphism problem for which no efficient solution is known. Surprisingly
enough however, in some cases the decision process can be simplified by
transforming the query graph into a "smaller" graph without changing the
answer. The main lesson learned is that the size of the query graph is not the
dominating factor, but its cycle rank. Although a number of our results hold specifically for undirected,
unlabelled graphs, we propose a more general framework and give many positive
and negative results for more general cases, where the graphs are labelled with
elements of a (finitely generated abelian) group.
