Complexity of Partition Problems

分区问题的复杂性

• 批准号: RGPIN-2014-05508
• 负责人: Hell, Pavol
• 金额: $ 4.52万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=611679
• 关键词: Complexity; 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.

图的着色是一个基本的图优化问题，从著名的四色定理到它在调度和运筹学中的应用，都是图论和算法的研究热点。本提案解决了与k着色问题相关的基本计算问题，以及它的两个重要推广，即h着色问题和m划分问题。这些问题之所以引起人们的兴趣，主要是因为它们分别与约束满足问题和图完备性的研究有关。