[The following abstract is taken from the preapplication (Form 180) to my most recent NSERC Discovery Grant application and was written in the summer of 2007. Its original purpose was to enable the NSERC committee to choose referees for my application.]
My work addresses problems for which there is evidence (such as NP-hardness) of intractability, but which may admit efficient solutions for special cases. In the period covered by my list of contributions, I have been working in the areas of fixed-parameter tractable algorithms and parameterized complexity, and propose to continue work in this area.
Many apparently intractable problems have a natural parameter associated with them and turn out to be tractable if that parameter is bounded. For example, finding a set of K vertices that touch all edges of a graph of N vertices or proving that no such set exists is NP-hard, and no algorithm with running time polynomial in N is believed to exist. In contrast, the problem can be solved in time linear in N if K is fixed (with an additive term that is exponential in K). Such a problem is called "fixed-parameter tractable" or FPT. Part of my work involves finding FPT algorithms.
Other problems appear to be difficult even when their parameters are bounded. If the set of K vertices is required to have no edges with both ends in the set, then there is evidence (akin to NP-hardness) that there is no algorithm with running time less than N to the power of a linear function of K and thus no FPT algorithm for the problem exists. This is an example of a result in parameterized complexity, which naturally complements the search for FPT algorithms.
These areas are related to the study of graphs of bounded treewidth and pathwidth (generalizing linear paths and branching trees), on which I have worked in the past, and exact algorithms (which work for all inputs with improved though perhaps still superpolynomial running time) on which I will also work in the near future. My general strategy has been, and will be, to extend algorithmic techniques to solve problems while simultaneously looking for limitations (hardness results and lower bounds) on the scope of these techniques.
Some of my past and proposed work involves fundamental problems defined on graphs (e.g. matching, covering, and packing) where the intent is to provide general solutions applicable in a number of contexts. Other work focusses on problems defined on particular mathematical structures arising from computational demands in particular areas of application (e.g. visual layout, logical satisfiability, database schemes, bioinformatics) whose practitioners may be relatively unaware of these new techniques.