Counting List Matrix Partitions of Graphs
From MaRDI portal
Abstract: Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is chosen from a given list so that no edge of G maps to a 0 in M and no non-edge of G maps to a 1 in M. Many important graph-theoretic structures can be represented as list M-partitions, such as graph colourings, split graphs and homogeneous sets and pairs, which arise in the proofs of the weak and strong perfect graph conjectures. There has been quite a bit of work on determining for which matrices M computations involving list M-partitions are tractable. We focus on counting list M-partitions, given a graph G and a list for each vertex of G. We identify a set of "tractable" matrices and give an algorithm that counts list M-partitions in polynomial time for every (fixed) matrix M in this set. The algorithm uses data structures such as sparse-dense partitions and subcube decompositions to reduce each instance to a sequence of instances in which the lists restrict access to portions of M in which the interaction of 0s and 1s is controlled. We solve the resulting restricted instances by converting them into counting constraint satisfaction problems (#CSPs) which we solve using arc-consistency. For every matrix M for which our algorithm fails, we show that counting list M-partitions is #P-complete. Further, we give an explicit characterisation of the dichotomy theorem: counting list M-partitions is in FP if M has a structure called a derectangularising sequence; otherwise, 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 lists can be used to encode cardinality restrictions in M-partitions problems and use this to give a polynomial-time algorithm for counting homogeneous pairs in graphs.
Recommendations
- Counting partitions of graphs
- List matrix partitions of graphs representing geometric configurations
- List matrix partitions of chordal graphs
- Partitions in matrices and graphs
- Counting connected set partitions of graphs
- scientific article; zbMATH DE number 15161
- The list partition problem for graphs
- Matrix partitions of split graphs
- Counting 4 4 matrix partitions of graphs
- Matrix partitions of perfect graphs
Cites work
- Algorithmic graph theory and perfect graphs
- An algorithm for finding homogeneous pairs
- An effective dichotomy for the counting constraint satisfaction problem
- Bi‐arc graphs and the complexity of list homomorphisms
- Bull-free Berge graphs are perfect
- Counting partitions of graphs
- Full Constraint Satisfaction Problems
- scientific article; zbMATH DE number 1472140 (Why is no real title available?)
- scientific article; zbMATH DE number 1545676 (Why is no real title available?)
- List homomorphisms and circular arc graphs
- List homomorphisms to reflexive graphs
- List Partitions
- Normal hypergraphs and the perfect graph conjecture
- Partitions of graphs into one or two independent sets and cliques
- The Complexity of the Counting Constraint Satisfaction Problem
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The strong perfect graph theorem
- The structure of hereditary properties and colourings of random graphs
- Towards a dichotomy theorem for the counting constraint satisfaction problem
Cited in
(4)
This page was built for publication: Counting List Matrix Partitions of Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944567)
