Complexity of Partition Problems

点击翻译按钮获取中文摘要

Graph colouring is a basic graph optimization problem whose study dominates graph theory and algorithms, from the celebrated four-colour theorem to its applications in scheduling and operations research. This proposal addresses fundamental computational questions connected with the problem of k-colouring, as well as two of its important generalizations, namely the H-colouring, and the M-partition problems. These are mainly of interest because of their connection with the constraint satisfaction problem, and with the study of graph perfection, respectively. It is well known that each k-colouring problem is NP-complete or polynomial time solvable. In the more general context of constraint satisfaction problems, such dichotomy has been conjectured by Feder and Vardi. In the most general form of M-partitions, the existence of dichotomy is also open. The Feder-Vardi conjecture has been driving theoretical research in constraint satisfaction for the past two decades. While there is now a natural conjecture for a classification of which H lead to polynomial time solvable problems (one version of such a conjecture is formulated in terms of existence of certain "polymorphisms"), the Feder-Vardi conjecture still seems beyond reach. On the other hand, there are many natural combinatorial problems arising from the conjecture that need to considered, and might impact the search for an answer. These include problems of classifying digraphs possessing particular polymorphisms, their relation to existing and well studied graph classes such as interval and chordal graphs, and the recognition and characterization problems for such digraphs. At the same time, the dichotomy conjecture and classification, as well as the basic k-colouring problem and the more general M-partition problems, appear to be more accessible, and worthy of study, for restricted classes of digraphs. In fact, the restriction of the Feder-Vardi conjecture to undirected graphs is a well-known result of Nesetril and the proposer, that was one of two main motivations for the Feder-Vardi conjecture. This work has potential impact on the understanding of the difficulties in solving constraint satisfaction problems. Constraint satisfaction problems model many problems in scheduling, logistics, databases, and artificial intelligence.