24
$\begingroup$

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula where you need to run over all conjugacy classes of the symmetric group $S_n$ and the number of conjugacy classes in $S_n$ is the number of partitions of the number $n$ known to behave like $\exp (\sqrt n )$. (There is a famous approximation for the partition function by Hardy and Ramanujan and subsequent expansions.)

Question 1: Is there a better algorithm? Can you improve the number of steps below $\exp (\sqrt n)$?

(Actually, I would be interested also by a different algorithm even if not better.)

While at it:

Question 2 (updated): What is the smallest number of arithmetic operations for an algorithm to count the number of partitions of an integer $n$?

(I asked originally about a better than $\exp (\sqrt n)$ time algorithm for counting the number of partitions of an integer n, but Sasho indicated an $O(n^{3/2}$ algorithm.)

Question 3: Since Questions 1 and 2 are questions with a "tiny input" (a single integer $n$) is computational complexity theory adequate to ask and offer useful answers (reductions etc.) to these (and similar) question?

Question 4: How much better can you do if you want only to approximate the number of isomorphism types by Polya theory or by other means?

Question 5: What is the complexity of sampling precisely or approximately isomorphism types of graphs with $n$ vertices?

Question 6: What is the complexity of questions 1,4,5 if instead of dealing with all graphs on $n$ vertices we deal with subgraphs of an input graph $G$ with $n$ vertices. (This makes these problems ordinary "big input" problems. Here, I am not aware of a $\exp (\sqrt n$) algorithm.

Question 7: Are these problems related in some way to the graph isomorphism problem?

$\endgroup$
  • 2
    $\begingroup$ Gil, does the following answer Question 2 or did I misunderstand? Euler's pentagonal number theorem gives a recursion for computing the number of partitions $p(n)$ of $n$. $p(n)$ is expressed as an alternating sum of $O(\sqrt{n})$ partition numbers of smaller $n$. This should give a dynamic programming algorithm for $p(n)$ with $O(n^{3/2})$ arithmetic operations. $\endgroup$ – Sasho Nikolov Sep 29 '13 at 4:13
  • 2
    $\begingroup$ Yes this is a very nice idea, and (I suspect there might be even easier ways to do it). Still interesting what's the bast algorithm is. Maybe we can do something like that for graphs??? $\endgroup$ – Gil Kalai Sep 29 '13 at 5:44
  • 2
    $\begingroup$ In case anyone else was wondering what the known values for the number of graphs for small n are: see oeis.org/A000088 — there are also some asymptotic formulas there that might be relevant for question 4. $\endgroup$ – David Eppstein Sep 29 '13 at 6:47
  • 1
    $\begingroup$ Gil, I am thinking about the graph question. BTW, in the comment above I only indicated the number of arithmetic operations, but they will be on very large numbers (requiring $\Theta(\sqrt{n})$ bits to write down), so you probably should expect the algorithm will have actual running time $O(n^2)$. $\endgroup$ – Sasho Nikolov Sep 30 '13 at 4:41
  • 4
    $\begingroup$ To Question 4: how close an approximation do you want? The number of isomorphism types is asymptotically equal to $2^{\binom{n}{2}}/n!$, and in fact is equal to $(1+\varepsilon(n))2^{\binom{n}{2}}/n!$ where $\varepsilon(n) \to 0$ exponentially fast, so just outputting $2^{\binom{n}{2}}/n!$ gives you a very good approximation... $\endgroup$ – Joshua Grochow Mar 8 '18 at 7:39

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.