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
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758919
• 关键词: 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，可用于建模许多组合问题。 在这一领域有许多可牵引的问题，可以使学生进行良好的研究项目。 学生参与研究是我计划的特殊目的。