Difference between revisions of "Walther MA279 Spring2016 topic9" - Rhea

Revision as of 15:04, 24 April 2016

Group A: The Graph Isomorphism Problem

The Graph Isomorphism Problem

Introduction

The graph isomorphism problem has been a long-standing problem in complexity theory for the last four decades. The statement of the problem is fairly simple: Given any two finite graphs that may appear to be different, is there an "easy" way to tell whether or not the two graphs are the same? We'll look at the statement of the problem in a slightly more rigorous setting, discuss the importance of the problem in other fields, as well as some recent progress made on the problem by a professor at the University of Chicago.

Basic concepts

We'll start off with some basic concepts related to the problem and formulate a more rigorous statement of the problem.

$ \ \text{Definitions} $

• A $ \ \text{Graph } G $ is a pair of sets $ \ G = (E_{G}, V_{G}) $ , where $ \ V_{G} $ is the set of vertices (or "dots") in the graph and $ \ E_{G} $ is the set of edges (or "lines") for the graph.

• A $ \ \text{Graph Isomorphism } f $ between two graphs $ \ G \text{ and } H $ is a bijective function $ \ f : V_{G} \rightarrow V_{H} $ with the property that there is an edge between $ \ v_{i} \text{ , } v_{j} \in V_{G} $ if and only if there is an edge between $ \ f(v_{i}) \text{ , } f(v_{j}) \in V_{H} $ . In other words, this is a one-one correspondence between $ \ G \text{ and } H $ showing that they are in fact the same graph. One example of a graph isomorphism is the following:

Applications

Isomorphic graphs have a lot of applications nowadays. All the entities in the world can be represented by some sort of connections. A big part of today's technology is to figure out these connections and relations. Every time when we show an isomorphism between such relations with graphs, a new star starts to shine on the firmament of human thinking power.

Listed below are some of the more concrete areas that use graph isomorphism:

• In automata theory. There are multiple uses. The main one is to show that some two languages are equal.
• In parallel processing: to reason about behavior of complex systems.
• In verification of things: e.g. computer programs, logic proofs, or even electronic circuits.
• In compilers. e.g. perform optimizations.
• In search engines that use formulas more sophisticated than words. e.g. in biology DNA structures.
• Security. e.g. fingerprints scanners, facial scanners, and retina scanners.
• Civil engineering, city planning, building interior planning (e.g. recognizing geographic locations with desired properties).
• Analysis of social structures (special cases may include schools, military, parties, events, etc.).
• Analysis of business relations.
• Any system that performs clustering would benefit from fast graph-isomorphism algorithm, e.g.

     * linking two Facebook accounts of the same person
     * recognizing web users based on their behavior
     * recognizing plagiarism in students solutions

Computability

Algorithms

History

Special Cases