25
$\begingroup$

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.

$\endgroup$
8
  • 9
    $\begingroup$ Enumerate the finite graphs, assign to each graph its index in the sequence. Comparing the invariant is easy, calculating it, not so much. I assume you wanted some kind of restriction on the invariants, so this is excluded? $\endgroup$
    – Thorny
    Jan 13, 2010 at 8:53
  • $\begingroup$ That's funny: In <a href="mathoverflow.net/questions/11647/… most recent post</a> I try to make sense of this notion of naturality. And more than that: I definitely had your question at the top of my pipeline, but now I will postpone it and watch the discussion here. $\endgroup$ Jan 13, 2010 at 11:43
  • 4
    $\begingroup$ This seems to be a very difficult problem. You can think about the case of bounded degree graphs where it is known that graph isomorphism is in P. Still no set of invariants is known. (Do you have any suggestions for trees? for planar graphs?) For general graphs although there are good reasons to believe that graph isomorphism is in co NP there are also reasons to believe that showing it will be very hard. "Under deradomization" is not something to take lightly. (Here are some examples: gilkalai.wordpress.com/2009/12/06/four-derandomization-problems ) $\endgroup$
    – Gil Kalai
    Jan 13, 2010 at 13:23
  • $\begingroup$ Gil: one suggestion for trees is the chromatic symmetric polynomial (garden.irmacs.sfu.ca/?q=op/…). $\endgroup$ Jan 13, 2010 at 13:26
  • 3
    $\begingroup$ I do not see how to compare chromatic symmetric polynomials in P. In some sense comparing them (I am not even talking about calculating them) is more complicated than comparing the trees. You can regard the deck of isomorphism types of edge-deleted subgraphs (or vertex deleted subgraphs) as a kind of graph invariant of the type you want. $\endgroup$
    – Gil Kalai
    Jan 13, 2010 at 20:12

5 Answers 5

29
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The link to cs.trincoll.edu appears to be broken, but a copy is saved on the Wayback Machine. The full citation is: Miyazaki, Takunari, The complexity of McKay’s canonical labeling algorithm, Finkelstein, Larry (ed.) et al., Groups and computation II. Workshop on groups and computation, June 7–10, 1995, New Brunswick, NJ, USA. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 28, 239–256 (1997). Zbl 0878.05063. $\endgroup$ May 2, 2023 at 9:09
  • 1
    $\begingroup$ The link to springerlink.com is also broken. I'm also unable to find any snapshot saved on the Wayback Machine. Presumably, it is meant to point to the following paper: Cai, Jin-Yi; Fürer, Martin; Immerman, Neil, An optimal lower bound on the number of variables for graph identification, Combinatorica 12, No. 4, 389–410 (1992). Zbl 0785.68043. $\endgroup$ May 2, 2023 at 9:11
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Hmm. I don't know much invariant theory, but I think I get why this "should" work. That said, I'm not actually convinced this is in the spirit of the question either -- partly because I was hoping for a number of invariants independent of the order of the graph, but mostly because "turn it into algebra" doesn't really tell you much by itself (although this does look more approachable than something like "pick a canonical labeling by AoC.") Upvoted anyway, though, since it's technically right and something I hadn't thought about. $\endgroup$ Jan 13, 2010 at 7:19
  • $\begingroup$ This attaches to each graph a vector of zeroes and ones whose length depends on $n$ (but for which there are bounds), the spectrum attaches to each graph a vector of real numbers whose length also depends on $n$. $\endgroup$ Jan 13, 2010 at 7:27
  • $\begingroup$ By the way, this works because invariant functions separate orbits. $\endgroup$ Jan 13, 2010 at 7:35
  • $\begingroup$ Good point about the spectrum. This still feels a bit like sidestepping the question, but I'll sleep on it and maybe try to work out a small case by hand tomorrow, and see if my opinion changes. $\endgroup$ Jan 13, 2010 at 7:41
  • 1
    $\begingroup$ It is very hard to explicitely compute those invariants. For $n<=4$ you can do it by hand; for $n=5$ it was intractable last time I checked. See, for example, portal.acm.org/citation.cfm?id=377612 $\endgroup$ Jan 13, 2010 at 7:54
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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?)

$\endgroup$
1

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.