Two algorithms for general list matrix partitions

Abstract

List matrix partitions are restricted binary list constraint satisfaction problems which generalize list homomorphisms and many graph partition problems arising, e.g., in the study of perfect graphs. Most of the existing algorithms apply to concrete small matrices, i.e., to partitions into a small number of parts. We focus on two general classes of partition problems, provide algorithms for their solution, and discuss their implications.The first is an O(nr+2)-algorithm for the list M-partition where M is any r by r matrix over subsets of {0, 1}, which has the bisplit property. This algorithm can be applied to recognize so-called k-bisplit graphs in polynomial time, yielding a solution of an open from [2].The second is an algorithm running in time (rn)O(log r log n/log log n)nO(log2r) for the list M-partition where M is any r × r matrix over subsets of {0,1,...,q- 1}, with the incomplete property. This algorithm applies to all non-NP-complete list M-partition problems with r = 3, and it improves the running time of the quasi-polynomial algorithm for the stubborn problem from [5], and for the edge-free three-coloring problem from [12].