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