Complete graph invariants?

Question

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a combination of the two I listed will fail to distinguish between two random trees of the same size with high probability.

Is there a known set of graph invariants that does always distinguish between non-isomorphic graphs? To rule out trivial examples, I'll require that the problem of comparing two such invariants is in P (or at the very least, not obviously equivalent to graph isomorphism) -- so, for instance, "the adjacency matrix" is not a good answer. (Computing the invariants is allowed to be hard, though.)

If this is (as I sort of suspect) in fact open, does anyone have any insight on why it should be hard? Such a set of invariants wouldn't require or violate any widely-believed complexity-theoretic conjectures, and actually there are complexity-theoretic reasons to think that something like it exists (specifically, under derandomization, graph isomorphism is in co-NP). It seems like it shouldn't be all that hard...

Edit: Thorny's comment raises a good point. Yes, there is trivially a complete graph invariant, which is defined by associating a unique integer (or polynomial, or labeled graph...) to every isomorphism class of graphs. Since there are a countable number of finite graphs, we can do this, and we have our invariant.

This is logically correct but not very satisfying; it works for distinguishing between finite groups, say, or between finite hypergraphs or whatever. So it doesn't actually tell us anything at all about graph theory. I'm not sure if I can rigorously define the notion of a "satisfying graph invariant," but here's a start: it has to be natural, in the sense that the computation/definition doesn't rely on arbitrarily choosing an element of a finite set. This disqualifies Thorny's solution, and I think it disqualifies Mariano's, although I could be wrong.

Answer 1

A complete graph invariant is computationally equivalent to a canonical labeling of a graph. A canonical labeling is by definition an enumeration of the vertices of every finite graph, with the property that if two graphs are isomorphic as unlabeled graphs, then they are still isomorphic as labeled graphs. If you have a black box that gives you a canonical labeling, then obviously that is a complete graph invariant. On the other hand, if you have a complete graph invariant for unlabeled graphs, then you also have one for partially labeled graphs. So given a black box that computes a complete graph invariant, you can assign the label 1 to the vertex that minimizes the invariant, then assign a label 2 to a second vertex than again minimizes the invariant, and so on.

There are algorithms to decide graph isomorphism for certain types of graphs, or for all graphs but with varying performance, and there are algorithms for canonical labeling, again with varying performance. It is understood that graph isomorphism reduces to canonical labeling, but not necessarily vice versa. The distinction between the two problems is discussed in this classic paper by Babai and Luks.

One natural canonical labeling of a graph is the one that is lexicographically first. I think I saw, although I don't remember where, a result that computing this canonical labeling for one of the reasonable lex orderings on labeled graphs is NP-hard. But there could well be a canonical labeling computable in P that doesn't look anything like first lex.

As Douglas says, nauty is a graph computation package that includes a canonical labeling function. It is often very fast, but not always. Nauty uses a fancy contagious coloring algorithm. For a long time people thought that contagious coloring algorithms might in principle settle the canonical labeling and graph isomorphism problems, but eventually counterexamples were found in another classic paper by Cai, Furer, and Immerman. It was not clear at first whether this negative result would apply to nauty, but it seems that it does.

Answer 2

nauty provides a canonical labelling of a graph. Here's a link: http://cs.anu.edu.au/~bdm/nauty/

Answer 3

One can find generators for the ring of invariants of $\mathbb F_2[x\_{ij}:1\leq i < j \leq n]$ under the action of $S_n$ on the indices, which are finitely many by Noether's finite generation theorem. I think this gives you a complete set of invariants.

Later: As Steve observes, one would like the number of invariants not to grow too fast. In characteristic zero (which we may use just as well), Noether's bound tells us that the ring of invariants is generated by at most $\binom{n^2+n!}{n!}$ elements, but this is quite huge (for $n=6$ the bound is 48813025503084826957958990535221725233495346780817632847728425, which is discouraging...) I do not think anyone knows how many elements one really needs, though, to generate in this particular case---usually Noether's bound is pretty bad.

Answer 4

In some ways, provably, no (assuming the graphs are infinite). See MR1011177 (91f:03062) Friedman, H; Stanley, L; "A Borel reducibility theory for classes of countable structures." J. Symbolic Logic 54 (1989), no. 3, 894–914.

This paper shows (although the argument is terse, and at least some is older folklore) that any Borel (in an appropriate sense) function f mapping graphs to any thing else with an equivalence relation E in such a way that G is isomorphic to H iff f(g) E f(H) must be at least as complicated as the graphs themselves.

For a similar result on finite graphs, see MR2135387 (2006e:03049) Calvert, Cummins, Knight, and Miller, Comparing classes of finite structures. (Russian) Algebra Logika 43 (2004), no. 6, 666--701, 759; translation in Algebra Logic 43 (2004), no. 6, 374–392.

Answer 5

The sequence of homomorphism numbers $|Hom(F_i,G)|$ for all (isomorphism types of) graphs $F_i$ is an invariant of $G$ (see Lovász, Operations with structures).

(Does this fit your bill? Or do you want finite invariants only?)