Counting List Matrix Partitions of Graphs

Given a symmetric $D\times D$ matrix $M$ over \0,1,*\, a list $M$-partition of a graph $G$ is a partition of the vertices of $G$ into $D$ parts which are associated with the rows of $M$. The part of each vertex is chosen from a given list in such a way that no edge of $G$ is mapped to a 0 in $M$ and no nonedge of $G$ is mapped to a 1 in $M$. Many important graph-theoretic structures can be represented as list $M$-partitions including graph colorings, split graphs, and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. Thus, there has been quite a bit of work on determining for which matrices $M$ computations involving list $M$-partitions are tractable. This paper focuses on the problem of counting list $M$-partitions, given a graph $G$ and given a list for each vertex of $G$. We identify a certain set of “tractable” matrices $M$. We give an algorithm that counts list $M$-partitions in polynomial time for every (fixed) matrix $M$ in this set. The algorithm relies on data structures such as sparse-dense partitions and subcube decompositions to reduce each problem instance to a sequence of problem instances in which the lists have a certain useful structure that restricts access to portions of $M$ in which the interactions of 0s and 1s are controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (${\#CSP}$s), which we show how to solve using a constraint satisfaction technique known as arc-consistency. For every matrix $M$ for which our algorithm fails, we show that the problem of counting list $M$-partitions is ${\#P}$-complete. Furthermore, we give an explicit characterization of the dichotomy theorem: counting list $M$-partitions is tractable (in ${FP}$) if the matrix $M$ has a structure called a derectangularizing sequence. If $M$ has no derectangularizing sequence, we show that counting list $M$-partitions is ${\#P}$-hard. We show that the metaproblem of determining whether a given matrix has a derectangularizing sequence is ${NP}$-complete. Finally, we show that list $M$-partitions can be used to encode cardinality restrictions in $M$-partitions problems, and we use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.