×

Automating Pólya theory: The computational complexity of the cycle index polynomial. (English) Zbl 0785.20004

Let \(G\) be a group of permutations on an \(n\) element set, then Pólya’s cycle index polynomial of \(G\) is the \(n\)-variable polynomial \[ P_ G(x_ 1,\dots,x_ n)= (1/| G|) \sum_{g\in G} x_ 1^{c_ 1(g)}\cdots x_ n^{c_ n(g)} \] where \(c_ i(g)\) is the number of cycles of \(g\) of length \(i\). The evaluation problem is the following: Given a set of generators for a degree \(n\) group \(G\) and a sequence \(y_ 1,y_ 2,\dots\) of non-negative real numbers, evaluate \(P_ G(y_ 1,\dots,y_ n)\). It is shown that the evaluation problem is \(\#P\)-hard whenever there exists an \(i\) such that \(y_ i\neq y_ 1^ i\) and \(y_ i\neq 0\). To prove this, it is shown that even determining the coefficient of \(x^{n/i}\) is \(\#P\)-hard for every \(i\), \(i>1\), which divides \(n\). If for the sequence \(y_ 1,y_ 2,\dots\) it holds either \(y_ j=y_ 1^ j\) for every \(j>1\), or \(y_ 1=y_ 2=\dots=0\), then the evaluation problem is polynomially solvable.
Further, the approximate evaluation problem is considered. It is shown that it is NP-hard to approximately solve the evaluation problem if either there exists an \(i\) such that \(y_ i>y_ 1^ i\) or \(y_ 1=y_ 2=\dots=y\) for some positive non-integer \(y\). The combinatorial significance is presented of the cycle index polynomial and corollaries are derived for the computational difficulty of counting equivalence classes of combinatorial structures.
Reviewer: M.Demlová (Praha)

MSC:

20B40 Computational methods (permutation groups) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
05A15 Exact enumeration problems, generating functions
05A10 Factorials, binomial coefficients, combinatorial functions
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDFBibTeX XMLCite
Full Text: DOI