Browse Prior Art Database

GRAPH ISOMORPHISM, GENERAL REMARKS

IP.com Disclosure Number: IPCOM000128609D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 14 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

Gary L. Miller: AUTHOR [+3]

Abstract

TR18 fi An open question is the computational complexity of recognizing when two graphs are isomorphic. In an attempt to answer this question we shall analyze the relative com-putational complexity of generalizations and restrictions of the graph isomorphism problem" In the first section we show graph isomorphism of regular undirected graphs is complete over isomorphism of explicitly given structures (say Tarski models from logic). Then we show that valence seems to be important. Finally we analyze symmetric cubic graphs.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

GRAPH ISOMORPHISM, GENERAL REMARKS*

Gary L. Miller Departments of Mathematics and Computer Science The University of Rochester

TR18 fi An open question is the computational complexity of recognizing when two graphs are isomorphic. In an attempt to answer this question we shall analyze the relative com-putational complexity of generalizations and restrictions of the graph isomorphism problem" In the first section we show graph isomorphism of regular undirected graphs is complete over isomorphism of explicitly given structures (say Tarski models from logic). Then we show that valence seems to be important. Finally we analyze symmetric cubic graphs.

fiTR16 has been incorporated into this Technical Report.

*This research was supported in part by the National Research Council under Grant #NRC- A5549; in part by the Alfred P. Sloan Foundation under Grant #74-12-5; and in part by the Advanced Research Projects Agency of the Department of Defense, moni-tored by ONR under Contract #N00014-75-C-1091. A graph G is a set of edges over a set of nodes, nodes being denoted by N(G). The graph is undirected unless otherwise noted. The number of edges associated with. a node is the valence of the node. The valence of a graph is equal to the maximum over the valences of the nodes. A graph is said to be regular if all nodes have the same valence. We shall need the computational notations:

1) P(NP) is all sets recognizable in (non)deterministic polynomial time; and _ 2)

(Equation Omitted)

. denote that A is poly- nomial time reducible to B.

I. Completeness of Graph Isomorphism over Isomorphism

The main result of this Section is Theorem 2, which states that isomorphism of un-directed graphs is complete over the general isomorphism problem. We first state and prove a special case which contains most of the ideas and techniques to be used to prove the general case. Theorem I: Directed graph isomorphism < p undi-rected graph isomorphism. Proof: Suppose that G and G'are two directed graphs on n nodes. We define a map or proce-dure, say a, from directed graphs to undirected graphs, such that

(Equation Omitted)

Given G we construct a(G) as follows: I) For each node of G construct a node for a(G): 2) For each directed arc of G (say (X;Y)) construct a "gadget" using 7 new nodes and connect it to X and Y as in Figure 1.

(Image Omitted: Figure 1)

By the construction it should be clear that if g is an isomorphism of G onto G' then the natural extension of g to a(G) is also an iso-morphism of a(G) onto a(G'). Thus, to complete the proof of the theorem it suffices to prove the following lemma: Lemma: If g is an isomorphism from a(6)

University of Rochester Page 1 Dec 31, 1979

Page 2 of 14

GRAPH ISOMORPHISM, GENERAL REMARKS

onto a(G') then g restricted to the nodes of G is an isomorphism of G onto G'. Proof: The spectrum of a node X in a graph on n nodes is a sequence of natural

(Equation Omitted)

such...