Topological Parameter Choice for FPT Graph Algorithms

Graphs are one of the most expressive structures which mathematics has produced. They underpin applications in a great number of different fields such as computer science, network epidemiology, neuroscience, social science and statistical physics. Graphs are so successful because they abstractly represent relationships between objects; some examples of graphs may be a person's friendship network on Facebook, the national railway system or neurons connected by synapses in the human brain. However, on their own, they don't accomplish much: in order to do anything useful with these structures, we must construct algorithms which we may deploy in order to answer questions about any system we are interested in.

For example, during the cold war, the United States army was interested in finding the most efficient and effective way of disrupting the Soviet railway system. This military interest spawned theoretical work by Ford and Fulkerson which culminated in an algorithm which finds an efficient way of disconnecting a graph by deleting some of its edges. This algorithm always finds an optimal solution and is guaranteed to do so within a reasonable amount of time for all possible inputs. Unfortunately, graph problems for which we may find such elegant solutions are the exception rather than the rule: in most cases, we have to compromise on at least one of the optimality of the solution, the time that might be required in the worst case or the ability to deal with all possible inputs.

In practice, heuristic methods are often used to find an optimal solution, and often these will solve the problem within a reasonable amount of time. However, such methods have two significant shortcomings: there is no guarantee on the time that might be required for the algorithm to terminate (so we could, at any point, encounter an input on which the algorithm takes weeks rather than seconds), and moreover they provide very little theoretical insight into why an approach works.

With formal algorithms we may hope to resolve both of these issues, but if we do not wish to compromise on having guarantees of correctness and efficiency, we must restrict the input somehow: particularly fruitful from a theoretical point of view is the approach of decomposing a graph into more tractable substructures. However, a major limitation of the applicability of this approach in practice is that many of the decompositions which are known to be particularly useful in the theoretical design of algorithms (e.g. tree decompositions) are difficult to compute on all but small inputs, thus the running time of these decomposition-based algorithms is typically dominated by the time required to compute such a decomposition. Understandably, there is a great appetite for new and more practical ways to compute decompositions of algorithmic interest. My work will attempt to satiate this demand by drawing upon the recent impressive developments in discrete geometry and combinatorial and algebraic topology. This is a promising approach because, even if such methods do not give rise to results that apply to all graphs, it is particularly well-suited to applications which deal with graphs where there is some underlying geometric structure, which is the case for many of the inputs arising in real-world applications.

The project aims to obtain general results which will yield more practical ways of computing graph parameters of interest and it will focus on using the aforementioned geometric ideas from discrete differential geometry and topology. These ideas will be of inherent interest to the theoretical community and they also have the potential to render two decades-worth of work in this field more practically applicable, with potential impact on the state-of-the-art algorithms used to solve problems of real-world importance in areas as diverse as artificial intelligence, circuit design, scheduling problems, computer vision and robotics, and network epidemiology.