Complexity of Partition Problems

分区问题的复杂性

• 批准号: RGPIN-2014-05508
• 负责人: Hell, Pavol
• 金额: $ 4.52万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=653384
• 关键词: 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划分问题。这些问题之所以引起人们的兴趣，主要是因为它们分别与约束满足问题和图完备性的研究有关。**众所周知，每个k-着色问题都是np完全的或多项式时间可解的。在约束满足问题的更一般的背景下，这种二分法已经被Feder和Vardi推测出来。在最一般形式的m分区中，二分类的存在性也是开放的。在过去的二十年里，联邦-瓦尔迪猜想一直推动着约束满足的理论研究。虽然现在有一个分类的自然猜想，其中H导致多项式时间可解的问题（这种猜想的一个版本是根据某些“多态性”的存在来表述的），但联邦-瓦尔迪猜想似乎仍然遥不可及。另一方面，有许多需要考虑的由猜想产生的自然组合问题，并且可能影响对答案的搜索。这些问题包括对具有特定多态性的有向图进行分类的问题，它们与现有的和研究得很好的图类（如区间图和弦图）的关系，以及对这些有向图的识别和表征问题。与此同时，二分猜想和分类，以及基本的k着色问题和更一般的m划分问题，对于有向图的限制类似乎更容易理解，更值得研究。事实上，联邦-瓦尔第猜想对无向图的限制是Nesetril和他的提议者的一个著名的结果，这是联邦-瓦尔第猜想的两个主要动机之一。**这项工作对理解解决约束满足问题的困难有潜在的影响。约束满足问题模拟了调度、物流、数据库和人工智能中的许多问题。