Computational complexity of combinatorial problems: graph homomorphisms, packings, and good characterizations

组合问题的计算复杂性：图同态、打包和良好的表征

• 批准号: RGPIN-2014-04760
• 负责人: Brewster, Richard
• 金额: $ 1.8万
• 依托单位: Thompson Rivers University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=680093
• 关键词: Computational; complexity; combinatorial; problems; graph

The speed and power of modern computers is truly impressive. Given the regular announcements of more and more powerful super-computers, one might believe any reasonable problem can be solved, by brute force, in reasonable time. Surprisingly this is not the case. There are certain problems that seem intractable by nature. Classic examples of such problems include scheduling, vehicle routing, and facility location problems. **All of these problems may be viewed as assigning resources (time slots, routes, locations) to some consumer (exam writing students, vehicles, factories). The goal is to assign the resources in the most efficient way possible, subject to constraints restricting the assignments. In general, we call these Constraint Satisfaction Problems or CSPs. The challenge in computing the most efficient assignment is the sheer number of possibilities. For each resource there can be many ways to assign it to a consumer. Moreover, each choice one makes may affect what other choices can be made in the future. In this way we are forced to consider all the possible combinations of assignments of resources to consumers. For a fast computer to exhaustively search through all the possible combinations looking for the optimum assignment could take thousands of years. This is an example of "combinatorial explosion"; the sheer number of combinations defeats brute force solutions. More efficient algorithms, if they exist, must be employed.**The primary aim of my program is to understand the nature of these challenging combinatorial problems. It turns out that some of these problems contain (mathematical) structure. This structure can be exploited to produce efficient algorithms, i.e. we do not need to consider all possible resource assignments, but rather we can zoom-in on the optimal solution. On the other hand, some problems seem to lack sufficient structure to admit an efficient solution. At the highest level the goal of my program is to identify those CSPs which admit efficient algorithms (polynomial time solvable) and those which are intractable (NP-complete). Fundamentally, we would like to know if such a dichotomy of efficient versus intractable holds for all CSPs. **The efficient algorithms are typically based on mathematical structure known as "good characterizations". A good characterization guides one through the combinatorial explosion to an optimal solution for the CSP or to a proof that the CSP has no solution, i.e. there are too many constraints, at which point the search can stop. In order to use this mathematical structure, we often need to develop new mathematics (in the form of good characterizations for CSPs). The development of this theory can be used to solve particular CSPs, but more importantly, it gives insight into the fundamental dichotomy question above.**My research program focuses on combinatorial problems from graph homomorphisms and graph packings and coverings. In the case of graph homomorphisms I am particularly interested in edge-coloured variants. These are a special class of CSPs that are useful for modelling many combinatorial problems. There are many tractable problems in this area that make good student research projects. The engagement of students in research is a particular aim of my program.

现代计算机的速度和能力确实令人印象深刻。鉴于越来越多功能强大的超级计算机的定期发布，人们可能会相信，任何合理的问题都可以在合理的时间内通过蛮力解决。令人惊讶的是，情况并非如此。有些问题本质上看起来很难解决。这类问题的典型例子包括调度、车辆路线和设施选址问题。**所有这些问题都可以被视为将资源(时间段、路线、位置)分配给某些消费者(考生、车辆、工厂)。目标是以尽可能最有效的方式分配资源，但要受到限制分配的限制。一般而言，我们将这些约束满足问题称为CSP。计算最有效分配的挑战在于可能性的绝对数量。对于每个资源，可以通过多种方式将其分配给使用者。此外，一个人所做的每一个选择都可能影响到未来可以做出的其他选择。以这种方式，我们被迫考虑将资源分配给消费者的所有可能的组合。对于一台快速的计算机来说，彻底搜索所有可能的组合以寻找最佳分配可能需要数千年的时间。这是一个“组合爆炸”的例子；组合的绝对数量击败了暴力解决方案。必须采用更有效的算法，如果它们存在的话。**我的程序的主要目的是理解这些具有挑战性的组合问题的本质。事实证明，其中一些问题包含(数学)结构。可以利用这种结构来产生高效的算法，即我们不需要考虑所有可能的资源分配，而是可以放大最优解决方案。另一方面，一些问题似乎缺乏足够的结构来承认有效的解决方案。在最高级别，我的程序的目标是识别那些允许高效算法(多项式时间可解)和那些难以处理(NP-完全)的CSP。从根本上说，我们想知道这种有效与难以处理的二分法是否适用于所有CSP。**高效的算法通常基于被称为“良好表征”的数学结构。一个好的特征可以引导人们通过组合爆炸找到CSP的最优解，或者引导人们证明CSP没有解，即有太多的约束，在这一点上搜索可以停止。为了使用这种数学结构，我们经常需要开发新的数学(以CSP的良好表征的形式)。这个理论的发展可以用来解决特定的CSP问题，但更重要的是，它深入了解了上面的基本二分法问题。**我的研究项目集中在图同态和图填充和覆盖的组合问题上。在图同态的情况下，我对边色变体特别感兴趣。这是一类特殊的CSP，对许多组合问题的建模很有用。在这一领域有许多容易处理的问题，这些问题构成了很好的学生研究项目。让学生参与研究是我这个项目的一个特别目标。