Browse Prior Art Database

A POLYNOMIAL TIME ISOMORPHISM ALGORITHM FOR ALMOST ALL GRAPHS

IP.com Disclosure Number: IPCOM000128698D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 6 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

STANLEY M. SELKOW: AUTHOR [+3]

Abstract

A polynomial time algorithm is introduced which attempts to order the vertices of a graph, independent of the labels of the vertices. It is shown that the probability that the algorithm fails goes to 0 as the size of the graphs considered increases. This algorithm can be used to solve the graph isomorphism problem in polynomial time such that the probability of failure goes to 0 with increasing graph size. Key Words: Isomorphism, graph theory, probabilistic combinatorics, com- putational complexity.

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

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A POLYNOMIAL TIME ISOMORPHISM ALGORITHM FOR ALMOST ALL GRAPHS

STANLEY M. SELKOW

CS-78-33 November 1978

This work was supported in part by a University of Tennessee Faculty Summer Research Grant.

Abstract:

A polynomial time algorithm is introduced which attempts to order the vertices of a graph, independent of the labels of the vertices. It is shown that the probability that the algorithm fails goes to 0 as the size of the graphs considered increases. This algorithm can be used to solve the graph isomorphism problem in polynomial time such that the probability of failure goes to 0 with increasing graph size. Key Words: Isomorphism, graph theory, probabilistic combinatorics, com- putational complexity.

1. Introduction

A problem of great practical importance is the graph isomorphism problem, which involves deciding whether or not two given graphs are iso-morphic 1 7J. Although this problem has not been shown to be NP-complete, a polynomial time algorithm has not been found in spite of a large amount of research. A related and possibly more difficult problem is the coding problem for graphs. We use the restrictive sense of a code for a graph to be a total ordering of the graph's vertices which is independent of any labels assigned to the vertices. The existence of a polynomial time algorithm to compute a code for an arbitrary graph would imply that a polynomial time algorithm exists for solving the isomorphism problem, since one would only need to check if the codes of two given graphs were equal. However, it is possible that a solution to the isomorphism problem would not furnish a solution to the coding problem. Our object is to show that almost all graphs have a code which is computable in polynomial time, and consequently the isomorphism problem can be solved in polynomial time for almost all graphs.

2. Definitions

A graph G = (V,E) is a set V of vertices and a set E of edges, each edge being a set of a pair of vertices. Two graphs

(Equation Omitted)

and

(Equation Omitted)

University of Tennessee Page 1 Dec 31, 1978

Page 2 of 6

A POLYNOMIAL TIME ISOMORPHISM ALGORITHM FOR ALMOST ALL GRAPHS

are equal if

(Equation Omitted)

. Two graphs are isomorphic,if they can be made equal by an appropriate relabeling of the vertices of either of the graphs.

We say that "almost all graphs have a given property" i)f the proportion of all graphs on n vertices with this property goes to 1 as n goes to1]. In other words, assuming a uniform distribution over the set of all unlabeled graphs on n vertices, the probability that a random graph has the property is

(Equation Omitted)

In order to define a random variable with a uniform distribution over the set of all unlabeled graphs o.n n vertices, we first consider the set of all labeled graphs on n vertices. If the edge between each pair of vertices belongs to the graph with probability %, independent of the existence of the other edges, it f...