<p>Indeed, not only does that seem to not be the case for GI, but one can prove a separation for other problems assuming only <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span>. <a href="https://doi.org/10.1137/0213042" rel="nofollow noreferrer">Blass and Gurevich (SICOMP, 1984)</a> showed that there is an equivalence relation that has a polynomial-time canonical form, but where it's lex least canonical form is &quot;<span class="math-container">$\mathsf{\Delta_2 P}$</span>-complete&quot; in the sense that it is in <span class="math-container">$\mathsf{FP}^{\mathsf{NP}} = \mathsf{F\Delta_2 P}$</span> and it is <span class="math-container">$\mathsf{\Delta_2 P}$</span>-hard. (For more on related results, see <a href="https://doi.org/10.1016/j.ic.2011.01.006" rel="nofollow noreferrer">my paper with Fortnow</a>.) As pointed out for GI by<br />
Emil Jeřábek in the comments, the lex least representative of an equivalence class is basically ignoring the structure of the problem, just paying attention to the fact that it can be encoded in strings. Efficient canonical forms are likely to take more advantage of structure in the problem, as Babai's algorithm does (and its predecessors).</p>

CC BY-SA 4.0
2024-08-08T23:47:02.660Z
2024-08-08T23:47:02.660Z
Joshua Grochow
<p>Is graph canonization (GC) in NP? Is it NP-hard? If unknown, what would be your best guess and why?</p>
<p>GC is GI-hard (GI-completeness is unknown), with the graph isomorphism problem being in NP and a candidate for NP-intermediate (unknown if NP-complete/in P).</p>
<p><a href="https://ix.cs.uoregon.edu/%7Eluks/CanLabel.pdf" rel="nofollow noreferrer">Babai et al. (1978)</a> mention that finding the lexicographically smallest isomorphic graph is NP-hard. Does that tell us anything about GC in general? My intuition tells me that this is the easiest way to canonize a graph, which would imply that GC is NP-hard and therefore the <a href="https://cstheory.stackexchange.com/a/21660/51614">surprising</a> result <span class="math-container">$NP\subseteq QP$</span> since <span class="math-container">$GC\in QP$</span> according to <a href="https://par.nsf.gov/servlets/purl/10179675" rel="nofollow noreferrer">Babai (2019)</a>. So my intuition is likely wrong. Can someone explain to me how so?</p>
<h5>References</h5>
<ul>
<li>Babai, László et al. (1978): Canonical Labeling of Graphs. ACM.</li>
<li>Babai, László (2019): Canonical Form for Graphs in Quasipolynomial Time. Preliminary Report.</li>
</ul>

CC BY-SA 4.0
2024-08-08T16:26:28.037Z
Graph canonization is not a decision problem in the first place, hence it makes no sense to ask if it is in NP. (It is not a function problem in the usual sense either, but rather a class of function problems that all share a certain defining property, and the "complexity" of the problem loosely refers to the mimimal complexity of any problem from this class by an abuse of terminology.)
Emil Jeřábek
CC BY-SA 4.0
2024-08-08T16:31:53.150Z
Your intuition is directly contradicted by Babai (2019): the whole reason he obtains a quasipolynomial-time canonization algorithm is that he is doing something much more sophisticated than "lexicographically first isomorphic graph".
Emil Jeřábek
CC BY-SA 4.0
2024-08-08T17:29:22.623Z
@Emil Ah yes, I am referring to the [function problem extension](https://en.wikipedia.org/wiki/Function_problem) here. In my opinion, this [should be](https://stackoverflow.com/a/34302968/1692437) default. (:

Do you know why the lexicographic approach is harder than Babai's?
Julius Kunze
CC BY-SA 4.0
2024-08-08T17:37:06.077Z
The lexicographic definition is a trivial brute force construction, hence it cannot be expected to be efficient. Babai’s construction was designed to beat it. There would be no point in publishing a complicated construction if it were not better than the old one.
Emil Jeřábek
CC BY-SA 4.0
2024-08-08T23:48:37.157Z
I think asking whether GC is in TFNP (or NPMV) is still a type error. The issue is that a canonical form is not something that depends only on the input graph, you have to know how the canonical forms of different graphs relate to one another, and this can't be captured in the definition of TFNP / NPMV. Blass & Gurevich (and later, Fortnow and I) introduced complexity classes of equivalence relations precisely to talk about such issues. In our notation, I think your first question is better phrased as something like: is GI in $\mathsf{CF}(\mathsf{NPSV}_t)$?
Joshua Grochow
CC BY-SA 4.0
2024-08-09T01:10:43.913Z
@Joshua Agreed! Just like Emil described, I thought of GC not strictly as a problem, but as a class of problems of the form "Find a canonization for this graph, where the canonization function fulfills property X." over all properties X. "CS in NP?" and "Is CS NP-hard?" was my sloppy way of asking whether any of those are in TFNP / all of them are TFNP-hard. Perhaps that's equivalent to your formalization?
Julius Kunze
<graph-algorithms><complexity-classes><graph-isomorphism>
Graph canonization vs. NP
Julius Kunze
# Graph canonization vs. NP

(Asked by: username_0 on 2024-08-08)

Is graph canonization (GC) in NP? Is it NP-hard? If unknown, what would be your best guess and why?

GC is GI-hard (GI-completeness is unknown), with the graph isomorphism problem being in NP and a candidate for NP-intermediate (unknown if NP-complete/in P).

[Babai et al. (1978)](https://ix.cs.uoregon.edu/%7Eluks/CanLabel.pdf) mention that finding the lexicographically smallest isomorphic graph is NP-hard. Does that tell us anything about GC in general? My intuition tells me that this is the easiest way to canonize a graph, which would imply that GC is NP-hard and therefore the [surprising](https://cstheory.stackexchange.com/a/21660/51614) result $NP\subseteq QP$ since $GC\in QP$ according to [Babai (2019)](https://par.nsf.gov/servlets/purl/10179675). So my intuition is likely wrong. Can someone explain to me how so?

##### References

* Babai, László et al. (1978): Canonical Labeling of Graphs. ACM.
* Babai, László (2019): Canonical Form for Graphs in Quasipolynomial Time. Preliminary Report.

**Tags:** graph-algorithms, complexity-classes, graph-isomorphism

> **Comments:**
> **username_1**: Graph canonization is not a decision problem in the first place, hence it makes no sense to ask if it is in NP. (It is not a function problem in the usual sense either, but rather a class of function problems that all share a certain defining property, and the "complexity" of the problem loosely refers to the mimimal complexity of any problem from this class by an abuse of terminology.)  
> **username_1**: Your intuition is directly contradicted by Babai (2019): the whole reason he obtains a quasipolynomial-time canonization algorithm is that he is doing something much more sophisticated than "lexicographically first isomorphic graph".  
> **username_0**: @Emil Ah yes, I am referring to the [function problem extension](https://en.wikipedia.org/wiki/Function_problem) here. In my opinion, this [should be](https://stackoverflow.com/a/34302968/1692437) default. (:  Do you know why the lexicographic approach is harder than Babai's?  
> **username_1**: The lexicographic definition is a trivial brute force construction, hence it cannot be expected to be efficient. Babai’s construction was designed to beat it. There would be no point in publishing a complicated construction if it were not better than the old one.  
> **username_2**: I think asking whether GC is in TFNP (or NPMV) is still a type error. The issue is that a canonical form is not something that depends only on the input graph, you have to know how the canonical forms of different graphs relate to one another, and this can't be captured in the definition of TFNP / NPMV. Blass & Gurevich (and later, Fortnow and I) introduced complexity classes of equivalence relations precisely to talk about such issues. In our notation, I think your first question is better phrased as something like: is GI in $\mathsf{CF}(\mathsf{NPSV}_t)$?  
> **username_0**: @Joshua Agreed! Just like Emil described, I thought of GC not strictly as a problem, but as a class of problems of the form "Find a canonization for this graph, where the canonization function fulfills property X." over all properties X. "CS in NP?" and "Is CS NP-hard?" was my sloppy way of asking whether any of those are in TFNP / all of them are TFNP-hard. Perhaps that's equivalent to your formalization?  

---

## 1 answers

### Answer by username_2 on 2024-08-08. Score: 3

Indeed, not only does that seem to not be the case for GI, but one can prove a separation for other problems assuming only $\mathsf{P} \neq \mathsf{NP}$. [Blass and Gurevich (SICOMP, 1984)](https://doi.org/10.1137/0213042) showed that there is an equivalence relation that has a polynomial-time canonical form, but where it's lex least canonical form is "$\mathsf{\Delta\_2 P}$-complete" in the sense that it is in $\mathsf{FP}^{\mathsf{NP}} = \mathsf{F\Delta\_2 P}$ and it is $\mathsf{\Delta\_2 P}$-hard. (For more on related results, see [my paper with Fortnow](https://doi.org/10.1016/j.ic.2011.01.006).) As pointed out for GI by  
username_1 in the comments, the lex least representative of an equivalence class is basically ignoring the structure of the problem, just paying attention to the fact that it can be encoded in strings. Efficient canonical forms are likely to take more advantage of structure in the problem, as Babai's algorithm does (and its predecessors).


---

