The Membership Problem for Switching Classes with Skew Gains

Article type: Research Article

Authors: Hage, Jurriaan

Affiliations: Leiden Institute of Advanced Computer Science, P.0. Box 9512, 2300 RA Leiden, The Netherlands, e-mail: [email protected] home-page: http://www.wi.leidenuniv.nl/~jhage

Note: [] Address for correspondence: Leiden Institute of Advanced Computer Science, P.O. Box 9512, 2300 RA Leiden, The Netherlands

Abstract: Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching classes are equivalence classes of gain graphs under the switching operation. The membership (or equivalence) problem is important to the theory of switching classes. The problem is to decide for two given skew gain graphs, on the same underlying graph and having gains from the same group, whether or not they belong to the same switching class. We give efficient algorithms. If a certain skew gain graph in the switching class has only abelian gains, then we can reduce the membership problem to an elegant problem on anti-involutions. Finally we show that the word problem can be reduced to the general membership problem, thereby establishing undecidability of the latter for some groups.

Keywords: Switching of graphs, centralizer, bipartite graphs, complexity, groups, graphs

DOI: 10.3233/FI-1999-39403

Journal: Fundamenta Informaticae, vol. 39, no. 4, pp. 375-387, 1999