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。计算最有效分配的挑战是可能性的绝对数量。 对于每个资源，可以有许多方法将其分配给消费者。 此外，一个人所做的每一个选择都可能影响到未来可能做出的其他选择。 通过这种方式，我们不得不考虑将资源分配给消费者的所有可能组合。对于一台快速的计算机来说，穷尽所有可能的组合来寻找最佳分配可能需要数千年的时间。这是“组合爆炸”的一个例子;组合的绝对数量击败了蛮力解决方案。 更有效的算法，如果存在的话，必须使用。我的计划的主要目的是了解这些具有挑战性的组合问题的性质。 事实证明，其中一些问题包含（数学）结构。 这种结构可以用来产生高效的算法，即我们不需要考虑所有可能的资源分配，而是可以放大最优解。 另一方面，有些问题似乎缺乏足够的结构来承认一个有效的解决方案。 在最高层次上，我的程序的目标是确定那些CSP承认有效的算法（多项式时间可解）和那些是棘手的（NP完全）。从根本上说，我们想知道这种有效与棘手的二分法是否适用于所有CSP。有效的算法通常基于被称为“良好表征”的数学结构。一个好的特征引导人们通过组合爆炸找到CSP的最优解，或者证明CSP没有解，即有太多的约束，在这一点上搜索可以停止。为了使用这种数学结构，我们经常需要开发新的数学（以CSP的良好表征的形式）。这个理论的发展可以用来解决特定的CSP，但更重要的是，它提供了洞察基本的二分法问题上述。我的研究计划侧重于从图同态和图包装和覆盖的组合问题。 在图同态的情况下，我特别感兴趣的边着色的变种。 这些是一类特殊的CSP，对许多组合问题建模非常有用。 在这一领域有许多容易处理的问题，可以成为优秀的学生研究项目。 学生参与研究是我的计划的一个特殊目标。