×

Counting partitions of graphs. (English) Zbl 1260.68176

Chao, Kun-Mao (ed.) et al., Algorithms and computation. 23rd international symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-35260-7/pbk). Lecture Notes in Computer Science 7676, 227-236 (2012).
Summary: Recently, there has been much interest in studying certain graph partitions that generalize graph colourings and homomorphisms. They are described by a pattern, usually viewed as a symmetric \(\{0, 1, *\}\)-matrix \(M\). Existing results focus on recognition algorithms and characterization theorems for graphs that admit such \(M\)-partitions, or \(M\)-partitions in which vertices of the input graph \(G\) have lists of admissible parts. In this paper we study the complexity of counting \(M\)-partitions. The complexity of counting problems for graph colourings and homomorphisms have been previously classified, and most turned out to be #P-complete, with only trivial exceptions where the counting problems are easily solvable in polynomial time. By contrast, we exhibit many \(M\)-partition problems with interesting non-trivial counting algorithms; moreover these algorithms appear to depend on highly combinatorial tools. In fact, our tools are sufficient to classify the complexity of counting \(M\)-partitions for all matrices \(M\) of size less than four. It turns out that, among matrices not acccounted for by the existing results on counting homomorphisms, all matrices which do not contain the matrices for independent sets or cliques yield tractable counting problems.
For the entire collection see [Zbl 1258.68005].

MSC:

68Q25 Analysis of algorithms and problem complexity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI