Complexity of Partition Problems

分区问题的复杂性

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