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
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708215
• 关键词: 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，可用于对许多组合问题进行建模。 该领域有许多易于处理的问题，可以作为优秀的学生研究项目。 让学生参与研究是我的项目的一个特殊目标。