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，可用于对许多组合问题进行建模。在这一领域有许多可处理的问题，这些问题是很好的学生研究项目。让学生参与研究是我这个项目的一个特别目标。