I noticed that the most convenient way to deal with quotient structures (like the rational numbers or other equivalence classes) within ZFC is to select a unique representant from each equivalence class, which is possible due to global choice. Then I noticed that this strategy also seems to work quite well in practice, i.e. graph canonization is not really less practical than more general approaches to graph isomorphism. On a theoretical level however, it's hard to clear up the relation between graph canonization and graph isomorphism. The most basic problem is that graph canonization is not a decision problem, and there is no obvious way to reduce it to a decision problem either. In fact, it doesn't fit any problem type which comes to my mind!

Some computational problem types based on different types of requested output:

  • decision problem
  • optimization problem
  • search problem
  • counting problem
  • function problem

Some computational problem types based on different types of expected input:

  • offline/online problem
  • (non-)promise problem

Yuval Filmus suggests that it is a canonization problem. However, all publications about canonization problems seem to treat questions closely related to graph canonization. I would rather prefer a wider problem class, maybe invariant (property) problem could be a nice class, if it could be suitably nailed down (and formalized).

  • $\begingroup$ I think "ZFC" should be replaced with "NBG". $\;$ $\endgroup$ – user12859 May 30 '14 at 9:10
  • 3
    $\begingroup$ Why isn't it a function problem? Let $\mathcal{G}$ be the set of all graphs. When trying to solve graph canonization we are looking for a function $f: \mathcal{G} \rightarrow \mathcal{G}$ such that for all $f(G)=H$ it holds that $G \cong H$ and additionally for all $G \cong H$ it must hold that $f(G) = f(H)$. One might argue it is different from many other functional problems such as addition in the sense that there are many different functions fulfilling this condition as opposed to only one. $\endgroup$ – John D. May 30 '14 at 9:27
  • 1
    $\begingroup$ @user17410 I don't know whether it is a function problem. I thought that there is an exact definition of what it means to be a "function problem", and that one consequence of this definition is that we have: "For all function problems in which the solution is polynomially bounded, there is an analogous decision problem such that the function problem can be solved by polynomial-time Turing reduction to that decision problem." But this consequence doesn't apply to graph canonization, so I guessed that it cannot be "function problem". $\endgroup$ – Thomas Klimpel May 30 '14 at 10:17
  • $\begingroup$ @RickyDemer We still call this system ZFC, because it gives a nice feeling of continuity and old established tradition. Note that also C99 is still called C, even so it certainly is different from K&R C, and C++11 is still called C++, even so it is certainly different from C++89. Many people understand what is meant by ZFC, but almost nobody knows NGB, and that it is in fact the improved version of ZFC that we implicitly use today. $\endgroup$ – Thomas Klimpel May 30 '14 at 10:27
  • 2
    $\begingroup$ Graph canonization is a canonization problem. $\endgroup$ – Yuval Filmus May 30 '14 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.