31
$\begingroup$

Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those languages that are accepted by some nondeterministic Turing machine $M$ obeying the same resource bounds as are used to define $C$, but where $M$ is allowed to make at most $g(n)$ nondeterministic moves. (I am using the notation of Goldsmith, Levy and Mundhenk, instead of the original by Kintala and Fischer, and $n$ is the size of the input.)

My question:

Is there a constant $c\ge0$ such that GRAPH ISOMORPHISM is in $c\sqrt{n}$-$\mathsf{PTIME}$?

(Edit: Joshua Grochow pointed out that a positive answer to this question would imply an algorithm for GI that has better asymptotic runtime bounds than are currently known. I would therefore be happy to relax the bound, allowing $o(\sqrt{n}\log n)$ nondeterministic moves.)

Background

For every fixed constant $c \ge 0$, $\mathsf{PTIME} = {c\log n}$-$\mathsf{PTIME}$, as $c\log n$ nondeterministic moves create at most a polynomial number of configurations to explore deterministically. Moreover $\mathsf{NP} = \cup_c n^c\text{-}\mathsf{PTIME}$, and by means of padding one can exhibit NP-complete languages in $n^\varepsilon$-$\mathsf{P}$ for every $\varepsilon > 0$.

Kintala and Fischer observed that deciding if an input graph with vertices $V$ has a $(|V|/3)$-clique is $\mathsf{NP}$-complete, but is in $O(\sqrt{n})$-$\mathsf{PTIME}$. To see this, discard the vertices which have at most $|V|/3 - 2$ neighbours. If there are too few remaining vertices, then reject. Otherwise the remaining vertices form a graph of size $\Omega(|V|^2)$. Then guess a $|V|/3$-subset of vertices using $|V| = O(\sqrt{n})$ nondeterministic steps and verify that they form a clique in polynomial time.

Some other languages $L$ of dense graphs in $\mathsf{NP}$ are also in $O(\sqrt{n})$-$\mathsf{PTIME}$. This is the case for any problem where a subset of the vertices serves as a certificate, and the size of the input graph is $\Omega(|V|^2)$. Examples are the promise versions of Induced Path or 3-Colouring for the case of dense graphs. Other problems seem to require larger certificates, for instance a list of vertices defining a Hamiltonian circuit seems to require $\Omega(|V| \log |V|)$ bits. It is not clear to me whether one could use an amount of nondeterminism that is too small to guess the certificate to decide such problems.

Given that $n^\varepsilon$-$\mathsf{P}$ can contain NP-complete languages, it then seems interesting to ask where in the bounded nondeterminism hierarchy potentially easier languages fall. One might expect GI, as a language that does not seem to be NP-complete, to be in the hierarchy closer to $\log n$-$\mathsf{P}$ than to $n$-$\mathsf{P}$. However, the obvious certificate for GI specifies the map using $|V|\log |V|$ bits, which is $\omega(\sqrt{n})$.

Another way to think about this question: is specifying a map between the sets of vertices a shortest possible certificate for GI?

Edit: Some further (corrected) remarks follow, to address the comments of Joshua Grochow.

If a certificate uses $f(n) = \Omega(\log n)$ bits and can be checked in polynomial time, then brute force gives an algorithm for GI taking $poly(n)2^{O(f(n))} = 2^{O(f(n))}$ time. With a certificate of size $O(\sqrt{n})$, brute force gives an algorithm taking $2^{O(\sqrt{n})}$ time, while a certificate of size $O(\sqrt{n}\log n)$ yields a brute force approach taking $2^{O(\sqrt{n}\log n)}$ time. The long-standing upper bound of Luks is $2^{O(\sqrt{n\log n})}$ time, which is between these two bounds up to constant exponents.

These considerations suggest that there might be an alternative approach to GI. The approach of Luks seems to rely at its core on identifying a subset of generators of an associated group. A nondeterministic machine might therefore guess a subset of the group. These subsets could then be checked exhaustively to yield a deterministic algorithm. If the list of elements can be specified succinctly, either because the associated group is never much larger than the size of the graph, or because the number of generators required is always small, and checking each candidate subset does not take too long, then this might yield an alternative approach to GI.

  • Chandra M. R. Kintala and Patrick C. Fischer, Refining Nondeterminism in Relativized Polynomial-Time Bounded Computation, SIAM Journal on Computing 9(1), 46–53, 1980. doi:10.1137/0209003
  • Judy Goldsmith, Matthew A. Levy, Martin Mundhenk, Limited nondeterminism, SIGACT News 27(2), 20–29, 1996. doi:10.1145/235767.235769
  • László Babai and Eugene M. Luks, Canonical Labeling of Graphs, STOC 1983, 171–183. doi:10.1145/800061.808746
Improve this question
$\endgroup$
11
  • $\begingroup$ So, if the graph is given as adjacency matrix of size $n^2$ does that mean I can make a linear number of non-deterministic moves w.r.t to the vertex set size $n$? $\endgroup$
    – John D.
    Commented Apr 4, 2014 at 10:42
  • $\begingroup$ @user17410: Yes, the representation should not matter too much, as long as the size of any instance is $O(|V|^2)$. (If they are unreasonably padded to have size $\Omega((|V|\log|V|)^2)$ then of course the square root bound is enough.) $\endgroup$
    – András Salamon
    Commented Apr 4, 2014 at 12:09
  • 4
    $\begingroup$ I think you may be asking for an algorithm better than the best known... If I understand, a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm would yield a $2^{O(\sqrt{n})}$ deterministic algorithm. The current best known deterministic algorithm takes time $2^{O(\sqrt{n} \log^2 n)}$. $\endgroup$
    – Joshua Grochow
    Commented Apr 4, 2014 at 19:16
  • $\begingroup$ @AndrásSalamon: Brute force = $n!poly(n) \approx 2^{O(n \log n)}$ NOT $2^{O(\sqrt{n} \log^2 n)}$... Also, I don't see why a certificate of size $\sqrt{n}$ leads to a brute force algorithm of time $2^{\sqrt{n} \log n}$ rather than $2^{O(\sqrt{n})}$ - can you elaborate? Maybe I am missing something in the definition of the "PTIME" notation? $\endgroup$
    – Joshua Grochow
    Commented Apr 10, 2014 at 4:06
  • 1
    $\begingroup$ @MohammadAl-Turkistany: Maybe, but I'll have to think about it a bit. There are points in Babai's algorithm where, once the color-degree is below polylog it applies the bounded-deg GI test, as in the previous best algorithm, and it's not clear if one can either make the polylog deg GI test into polylog-bounded nondeterminism, or whether one can continue Babai's recursion further to get the degree down to, say, constant color-degree. If and when I figure that out I'll update my answer - if you have thoughts on this I'm happy to chat, but this is probably not the right place to work through it. $\endgroup$
    – Joshua Grochow
    Commented Jan 16, 2017 at 22:58

1 Answer 1

Reset to default
8
$\begingroup$

First, (as has now been edited into the question statement) a positive answer to your question would immediately improve the state of the art in worst-case bounds for graph isomorphism. For a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm yields a $2^{O(\sqrt{n})}$-time deterministic algorithm, but the current best known for GI is only $2^{O(\sqrt{n \log n})}$

Second, it is not even immediately clear to me whether or not the current best algorithm is in fact a $O(\sqrt{n \log n})-\mathsf{PTIME}$ algorithm, although the first part of it clearly is, in some sense. The algorithm first guesses a set of vertices of size $\sqrt{n/\log n}$ to individualize (Zemlyachenko's trick - see here for an exposition in English), which can be done by guessing $\sqrt{n \log n}$ bits nondeterministically. However, after guessing those and individualizing (in deterministic poly time), it applies the best-known bounded-degree isomorphism test, which takes time $n^{O(d /\log d)}$ (Theorem 9.1 of this paper), and applies it in the case of $d=O(\sqrt{n \log n})$. I'd have to think carefully about whether the latter algorithm could be turned into a $O(\sqrt{n \log n})-\mathsf{PTIME}$ algorithm (seems like an interesting question...)

Improve this answer
$\endgroup$
12
  • $\begingroup$ Do you have links to versions not behind a paywall? I have never seen an actual implementation of Zemlyachenko's trick or the bounded degree isomorphism test. Partitioning vertices by degree like NAUTY speeds things up, but those with the same degree you still have to check all prime cycle permutations on them AFIK. $\endgroup$
    – Chad Brewbaker
    Commented Apr 11, 2014 at 14:39
  • $\begingroup$ @Chad: I'm unfortunately not aware of non-paywalled versions of those articles. However, Zemlyachenko's trick is quite simple to implement in practice and essentially reduces the degree. For practical implementation of Zemlyachenko's trick, i think the only question is the trade-off between enumerating sets of vertices to individualize (exponential in the size of the set) and any potential gains made by effectively reducing the degree. I do not know if it is actually implemented in NAUTY or other practical isomorphism algorithms. $\endgroup$
    – Joshua Grochow
    Commented Apr 11, 2014 at 17:10
  • $\begingroup$ @Chad: By the way, testing prime cycle permutations only suffices for detecting a nontrivial automorphism; it does not suffice for testing isomorphism. For example, if $G$ is a graph without nontrivial automorphisms, let $\pi$ be any permutation - not necessarily a prime cycle. Then $\pi(G)$ is isomorphic to $G$, and $\pi$ is the only isomorphism between $G$ and $\pi(G)$. But this isomorphism would not be detected by only considering prime cycles. $\endgroup$
    – Joshua Grochow
    Commented Apr 11, 2014 at 17:55
  • $\begingroup$ At the cost of doubling $n$, ISO can be computed with AUT by putting both graphs in an adjacency matrix. $\endgroup$
    – Chad Brewbaker
    Commented Apr 11, 2014 at 19:58
  • 1
    $\begingroup$ @VS. I don't think so. For example, $n$-PTIME includes languages decidable by an algorithm which uses n nondeterministic bits and takes $O(n^2)$ time, but $\mathsf{NTIME}(n)$ (probably) does not include all such languages. $\endgroup$
    – Joshua Grochow
    Commented Dec 31, 2019 at 8:09

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.