The Oxford Advanced Seminar on Informatic Structures

Introduction to OASIS

Michaelmas 2004

Hilary 2005

Trinity 2005

Simon Gay

Dov Gabbay

Philippe Jorrand

Michael Fellows

Mai Gehrke

Michaelmas 2005

Hilary 2006

Trinity 2006

Michaelmas 2006

Hilary 2007

Trinity 2007

Michaelmas 2007

Hilary 2008

Trinity 2008

Michael Fellows

TITLE: Structural parameters: good, bad and ugly

ABSTRACT: The field of parameterized complexity and algorithmics is concerned with the effect of structural parameters of the input on the computational complexity of problems. For example, it is well-known that many NP-hard problems concerning graphs can be solved efficiently for graphs of bounded treewidth, and this parameter turns up frequently in realistic applications. Treewidth is a {\it good} parameter because determining whether a graph has bounded treewidth, and finding a bounded width structural decomposition for the graph to exploit in algorithms for hard problems on such graphs, can be accomplished in FPT time, that is, in time $f(k)n^c$ for a small fixed constant $c$ and an $f(k)$ that is not too fast growing. For planar graphs, however, there is an even better structural parameter, {\it branchwidth}, that is ``nearly the same'' as treewidth: a graph has bounded branchwidth if and only if it has bounded treewidth, and the bounds differ by at most only a factor of 3. Branchwidth is a {\it better} parameter because it can be computed in polynomial time for planar graphs, while treewidth is NP-hard in this setting. This raises the general question: when a structural parameter seems interesting (e.g., useful for devising efficient algorithms) --- how good is it? There seem to be a lot of interesting parameters, and much current research is aimed at finding more of them,

for various applications. {\it Topological bandwidth} is an interesting parameter in this sense, but it is a {\it bad} parameter: it is $W[1]$-hard to compute. But it is not {\it ugly}. Similarly to the situation with branchwidth and treewidth for planar graphs, a graph has bounded topological bandwidth if and only if it has bounded {\it cutwidth} (with a difference of at most a factor of 2), and cutwidth is a good parameter. Of the many structural parameters currently of interest: Which are good? Which are bad? Which (if any) are ugly?