12. Géométries Multiples II – Roger Vilder

Roger Vilder (FR)

Géométries multiples II

Texts by Samuel Fiorini

It is important, albeit very difficult, to prove that two graphs are isomorphic. The problem has been much written about since the introduction of graph theory. In 2015, Hungarian mathematician László Babai found a new, much faster algorithm to solve it (theoretically speaking).

Read a fascinating article about it here.
And like all important problems, the graph isomorphism problem has its own Wikipedia page.

The graph isomorphism problem plays a particular role in theoretical computer science, a branch that is very closely related to mathematics. For half a century, theoretical computer scientists have worked on a variety of very complex problems including the one regarding graph isomorphism.

Although efficient algorithms have been found for certain problems, in other instances, no efficient one seems to exist.

(In complexity theory, an algorithm is efficient if the function which gives its computation time has polynomial type growth, the variable being the size of the instance.) 

To get a clearer picture, theoretical computer scientists aim to list problems in classes according to their increasing level of difficulty. For decision problems, like the one that concerns us here, the two most important complexity classes are \(P\) and \(NP\):

  • Class \(P\) problems can be solved in Polynomial (\(P\)) time by efficient algorithms.
  • Class \(NP\), which contains \(P\), includes problems for which the answer YES can be efficiently verified. 

For example, if two graphs are isomorphic, there is isomorphism from one graph to the other; it is easy to verify if a given bijection is an isomorphism. (Determining, however, if an isomorphism exists is far from simple. That is the whole problem!)

Thus, the problem of isomorphism belongs to \(NP\), as are many other interesting problems, including many problems formulated thanks to graphs.

There is a subset of problems in \(NP\) which are the hardest to solve (akin to the indomitable Gauls in ancient France). The so-called \(NP\)-complete problems are the most complex in \(NP\). They are all equivalent in the sense that if one of them admits an efficient algorithm, then all of them do.

The vast majority of \(NP\) problems are known to be in \(P\) or to be \(NP\)-complete. For example, the shortest path problem is in \(P\). This problem can be summarized by this question:

Given data in graph \(G\), two vertices \(x\) and \(y\), and a number \(D\),
is there a path from \(x\) to \(y\) whose length is shorter or equal to \(D\)?

Strangely enough, the longest path problem is \(NP\) complete:

Given data in graph \(G\), two vertices \(x\) and \(y\), and a number \(D\),
is there a path from \(x\) to \(y\) whose length is longer or equal to \(D\)?

This problem is of little importance in everyday life; most of us aim for efficiency. It may, however, be interesting for travelling salespeople or politicians. Go to the following link to learn more.

The graph isomorphism problem has a particularity: it is not known to be in \(P\) or to be \(NP\)-complete. Therefore, it may be one of the rare problems in the complexity class \(NP\)-intermediate, because it is harder than the problems in \(P\), but easier than any \(NP\)-complete problem.

A one-in-a-million fascinating problem!
All bets are on that this is far from over!

Samuel Fiorini
Associate Professor
Algebra and Combinatorics
Département de mathématique
Université libre de Bruxelles – ULB

Pages: 1 2 3