1
$\begingroup$

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) 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 result $NP\subseteq QP$ since $GC\in QP$ according to Babai (2019). 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.
Improve this question
$\endgroup$
6
  • $\begingroup$ 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.) $\endgroup$
    – Emil Jeřábek
    Commented Aug 8 at 16:26
  • 2
    $\begingroup$ 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". $\endgroup$
    – Emil Jeřábek
    Commented Aug 8 at 16:31
  • $\begingroup$ @Emil Ah yes, I am referring to the function problem extension here. In my opinion, this should be default. (: Do you know why the lexicographic approach is harder than Babai's? $\endgroup$
    – Julius Kunze
    Commented Aug 8 at 17:29
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Aug 8 at 17:37
  • $\begingroup$ 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)$? $\endgroup$
    – Joshua Grochow
    Commented Aug 8 at 23:48

1 Answer 1

Reset to default
3
$\begingroup$

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) 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.) As pointed out for GI by
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).

Improve this answer
$\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.