Publication details
Two Algorithms for General List Matrix Partitions
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Citation | |
| Description | 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(n(r+2))-algorithrn for the list M-partition problem 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 problem from [2]. The second is an algorithm running in time (rn)O(logr log n/ log log.n)(n)O(log(2)r) for the list M-partition problem where M is any r x 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]. |