Notions of width for directed graphs and hypergraphs: foundations and applications
1st November 2007 to 31st October 2010
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.