4
$\begingroup$

Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.

Let us call a (numerical) invariant $\alpha$ is good if it is, roughly speaking,

  1. simple to compute,
  2. fast to compute, and
  3. when applied to a family of graphs, say the family $\mathcal{G}_n$ of all graphs of order $\leq n$, the graphs fall into relatively small classes with different $\alpha$-values, that is, $$\lim_{n\ \longmapsto\ \infty}\frac{\max(\text{class sizes})}{\#\mathcal{G}_n}\longrightarrow0.$$

For example, the size of graphs are good invariants as it satisfies the conditions (1), (2), and (3) in the family $\mathcal{G}_n$ of all graphs of order $\leq n$. However, this is not true for the order of graphs in this family. The spectrum can be a candidates in this family, but it is not good in the family of trees.

One technique to overcome the isomorphism problem in large family of graphs is to use good invariants to put graphs into non-isomorphic classes and then try isomorphism check inside each class.

The question is what are best good invariants?

$\endgroup$
16
  • $\begingroup$ The number of edges is a good invariant too. $\endgroup$
    – Wojowu
    Jan 25, 2019 at 16:22
  • 1
    $\begingroup$ I like the (absolute value of the) determinant of the adjacency matrix (for connected graphs). Gerhard "Still Wants Even More Invariants" Paseman, 2019.01.25. $\endgroup$ Jan 25, 2019 at 16:48
  • 1
    $\begingroup$ @Wojowu, I think "size" here is being used to mean the number of edges, in contrast to "order" for number of vertices. $\endgroup$
    – Ben Barber
    Jan 25, 2019 at 16:58
  • 2
    $\begingroup$ Maybe the ordered list of vertex degrees? I think networkx (python graph library) uses that a fast not-isomorphic checker. You might want to check that library for similar functions. (You can turn this into a numerical invariant using an infinite sequence of rationally linearly independent irrational numbers, but this is not good for computing because of precisiob, and I see no reason why not to allow vector valued invariants into your question.) $\endgroup$
    – Elle Najt
    Jan 25, 2019 at 18:04
  • 1
    $\begingroup$ @Wlod AA Here, $\mathcal{G}_n$ ias considered as the familt of all graph sith at most $n$ vertices, so $\#\mathcal{G}_n=2^{\binom{1}{2}}+\cdots+2^{\binom{n}{2}}$, but once can restrict oneself to just graphs with $n$ vertices too. $\endgroup$ Jan 26, 2019 at 11:03

1 Answer 1

9
$\begingroup$

Let me start my answer by noting that this is fundamentally the wrong approach to the problem of reducing a large set of graphs by isomorphism type. The best software (nauty, Bliss, Traces) can put a graph into canonical form in an amount of time similar to what testing two graphs for isomorphism takes. After canonical labelling, you can use a sorting algorithm (or a hash table if it fits in memory) to remove isomorphs quickly. The costly step (canonical labelling) is needed only once per graph, instead of isomorphism testing multiple times per graph.

The advantage of canonical labelling is even more stark if you have a large database of graphs, and you want to determine whether a new graph is already in the database.

Getting back to your question, there is no uniform answer that applies for all classes of graphs. Lorenzo mentioned vertex degrees and you can make that even much stronger by counting the neighbours of each vertex according to their degrees. But as soon as you need to process a large number of regular graphs, this invariant is completely useless. An invariant based on the number of vertices at each distance from each vertex will work well on random regular graphs, but fail completely on strongly regular graphs or incidence geometries. And so on.

There is also the question of how the cost scales. An invariant that takes $n^3$ time to compute might be great when $n=20$, but when $n=10,000$ (well within range of modern programs except for very difficult graph classes) $n^3$ is too much.

The usual use of invariants is not to divide a file of graphs into parts, but to quickly distinguish vertices of each graph from each other as an aid to canonical labelling. But here again there are no known invariants that are efficient and effective for all graph classes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.