Counting list matrix partitions of graphs

Journal article

Given a symmetric D × 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 non-edge of G is mapped to a 1 in M. Many important graph-theoretic structures can be represented as list M-partitions including graph colourings, 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 is controlled. We show how to solve the resulting restricted instances by converting them into particular counting constraint satisfaction problems (#CSPs) 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 characterisation of the dichotomy theorem — counting list M partitions is tractable (in FP) if the matrix M has a structure called a derectangularising sequence. If M has no derectangularising sequence, we show that counting list M-partitions is #P-hard. We show that the meta-problem of determining whether a given matrix has a derectangularising 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.

Authors: Göbel, A; Goldberg, L; McQuillan, C; Richerby, D; Yamakami, T

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Journal: SIAM Journal on Computing
• Volume: 44
• Issue: 4
• Pages: 1089 - 1118
• Publication date: 2015-08-11
• Acceptance date: 2015-06-18
• DOI: 10.1137/140963029
• EISSN: 1095-7111
• ISSN: 0097-5397
• Language: English
• Keywords: matrix partitions of graphs; counting problems; #P-completeness; graph algorithms; complexity dichotomy