Graph Algorithms

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

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.********