Notions of width for directed graphs and hypergraphs: foundations and applications

A recently developed measure for graph complexity, tree-width, has proven very useful in the fields of graph structure theory and algorithms. Tree-width has helped establish a long standing conjecture in graph theory and led to the creation of similar structural measures, useful for solving other such problems. Additionally, as a measure of graph complexity it is well suited to developing large classes of efficiently solvable problems. Its success in both these fields has driven research to establish similar measures on more general structures such as directed graphs and hypergraphs, however, the full potential of these measures remains to be explored. This project will look at such measures with a view to establishing which properties of tree-width can and cannot be extended. In order to reach the objectives of the project, the work will be carried out in two parallel streams: a theoretical aspect intended to benefit the graph theory community by addressing some of the open problems that have arisen in the current work so far, and a practical aspect intended to benefit the algorithmic community by focussing on the complexity issues and producing deliverables such as algorithm implementations. Each stream will have two major components, with the intention of producing four significant contributions to the field over the course of the Fellowship. The theoretical stream will intially address a large class of current questions in the community by developing a framework for addressing monotonicity questions in graph pursuit games. The results of this will contribute towards the next area of work in this stream - investigating the structure theory of directed graphs and hypergraphs that results from extensions of tree-width. This work will aim to produce Courcelle-like theorems to determine large classes of tractable problems as well as investigate the feasability and usefullness of extending both measures to relational structures. This work will help establish a fruitful area for further research. The practical stream will be split between establishing complexity results, and developing a library of algorithms. The first of these will address the current complexity problems and then focus on developing practical definitions that improve on the known complexity bounds. The second will gather, improve and provide concrete implementations of the current work so far and, later in the project, provide concrete implementations of the results obtained.