Graph Algorithms

图算法

• 批准号: RGPIN-2016-06517
• 负责人: Cameron, Kathleen
• 金额: $ 2.26万
• 依托单位: Wilfrid Laurier 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=758489
• 关键词: Graph; Algorithms

A main direction of my research is to look for theorems which say that something that is easy to recognize always exists, and then to try to find what exists efficiently. The concepts “easy to recognize” and “efficiently” are formalized in computing theory as “in NP” and “polynomial time”. Informally this research direction can be stated as: if it's easy to recognize and you know it's there, surely it's not hard to find. (Anyone who has misplaced their keys at home may not agree!) This has led me to find efficient algorithms for unrelated problems I might not have considered before.Many theorems in mathematics state that the number of something is even (or odd). Usually they are proved by counting arguments. We use a different approach: we construct an “exchange graph”, where the “odd-degree” vertices correspond to the objects we want to show there is an even number of. Besides often providing a simpler proof, an exchange graph provides an algorithm for the problem: Given one object, find another. Since the number of objects is even, we know a second one exists. We are studying the efficiency of such algorithms, in particular for theorems concerning trees and cycles in graphs.Much of my research focuses on finding efficient algorithms for optimization problems on graphs such as minimum colouring and largest stable set. These problems have many applications including scheduling and in molecular biology. They are NP-hard for arbitrary graphs, which means that it is unlikely that efficient algorithms exist to solve them in general. However, graphs arising in applications often have special structure, which can sometimes be exploited to design efficient algorithms. I study specially structured graphs, where certain subgraphs are excluded or graphs with a nice intersection model. I try to discover properties of graphs in certain classes, to understand which properties are useful for solving which problems, and then use these properties to design efficient algorithms. Optimum matching is a well-solved problem with many applications including kidney exchange. Matchings in a graph correspond precisely to stable sets in its “line-graph”. Line-graphs are a subclass of “claw-free graphs” which are a subclass of “pan-free graphs”, and thus the stable set problem in either of these two specially-structured classes generalizes the matching problem. (A pan is a chordless cycle with at least four vertices together with a pendant edge.) Minty's (1980) efficient algorithm for maximum weight stable set in claw-free graphs led to much research on claw-free graphs, including the generalization of it by Brandstadt, Lozin and Mosca (2010) to pan-free graphs. Quite anomalously, these did not provide a defining system for the corresponding “stable set polytope”. Much ongoing work focuses on finding a defining system for claw-free graphs. I am studying the structure and the stable set polytope of subclasses of pan-free graphs.

我的研究的一个主要方向是寻找定理，说什么是容易识别的总是存在的，然后试图找到什么存在有效。“容易识别”和“有效”的概念在计算理论中被形式化为“在NP中”和“多项式时间”。非正式地说，这一研究方向可以表述为：如果它很容易识别，你知道它在那里，那么它肯定不难找到。（任何在家里放错钥匙的人都可能不同意！）这使我找到了解决以前可能没有考虑过的不相关问题的有效算法。数学中的许多定理都指出，某个东西的个数是偶数（或奇数）。它们通常通过计算参数来证明。我们使用不同的方法：我们构造了一个“交换图”，其中“奇数度”顶点对应于我们想要显示的对象，其中存在偶数个。交换图除了通常提供一个更简单的证明外，还提供了一个解决问题的算法：给定一个对象，找到另一个。由于物体的数量是偶数，我们知道存在第二个物体。我们正在研究这种算法的效率，特别是定理有关的树和周期在graphs. Most我的研究集中在寻找有效的算法优化问题的图，如最小着色和最大的稳定集。这些问题有许多应用，包括调度和分子生物学。它们对于任意图都是NP难的，这意味着不太可能存在有效的算法来解决它们。然而，在应用中出现的图往往具有特殊的结构，有时可以利用它来设计有效的算法。我研究特殊结构的图，其中某些子图被排除在外或具有良好交叉模型的图。我试图发现某些类中图的属性，了解哪些属性对解决哪些问题有用，然后使用这些属性来设计有效的算法。最佳匹配是一个很好解决的问题，有许多应用，包括肾脏交换。图中的匹配精确地对应于其“线图”中的稳定集。线图是“无爪图”的一个子类，无爪图是“泛自由图”的一个子类，因此这两个特殊结构的类中的任何一个中的稳定集问题都推广了匹配问题。（平移是至少有四个顶点和一个悬垂边的无弦循环。）Minty（1980）关于无爪图最大权稳定集的有效算法引起了对无爪图的大量研究，包括Brandstadt，Lozin和莫斯卡（2010）将其推广到泛无图。相当令人遗憾的是，这些并没有为相应的“稳定集多面体”提供一个定义系统。许多正在进行的工作集中在寻找一个定义系统的无爪图。我正在研究泛自由图的子类的结构和稳定集多面体。