** Find a list of GROW open problems here.** 

GROW is an invitation only, grass roots organized workshop held every odd year.  Information on the 2015 GROW can be found at: https://grow2015.sciencesconf.org/

This site also has links to previous workshops.

The GROW conference brings together experts in both theoretical and practical issues to design new strategies for dealing with intractable graph problems. One well-known problem-solving strategy decomposes the given problem into subproblems that can be solved independently, and then combines these solutions into an overall solution. Graph decompositions may lead to tractable instances of generally intractable problems by virtue of defining width parameters which, for some restricted but rich classes of graphs, can be bounded. Once such a decomposition is computed (hopefully in an efficient manner), a dynamic programming approach often produces an efficient solution.

From an historical perspective, classical modular decomposition was followed by other decomposition strategies including split decomposition and tree-decomposition, for which a powerful analytical tool became the concept of a minor (a minimal obstruction set, in general terms.) Tree-decomposition lead to the definition of tree-width, one possible parameter describing the complexity of a graph’s parsing. Subsequently, other graph-width parameters, such as branch-width and clique-width have been introduced and studied with respect to their structural and algorithmic properties. Often, classes of graphs defined by some structural properties have bounded width parameter values. In such cases traditional and newly discovered graph searching algorithms have been shown to be very effective in displaying the structure. Exploring the interplay of problems, graphs and width parameters is one of the main themes of the workshop.

The complexity of problems restricted to graphs with a bounded width parameter often depends on the value of that bound. For NP-hard problems, the complexity function often has that parameter in the exponent. Early theoretical results of Arnborg, Bodlaender, Courcelle and others indicate that some well defined classes of problems (namely those describable in extended monadic second order logic, MSOL) can be solved in polynomial time on graphs with constantly bounded width parameters. However, those solutions may still not be efficiently computable because of the magnitude (sometimes astronomical) of the constant factors involved.

The running time of an algorithm is usually expressed as a function of various parameters of the input including its input size. For many problems, this function can be represented so that its dependence on the input size and on another significant parameter k (eg., the treewidth of the input graph) can be separated. For some problems thought to be inherently intractable (NP-hard), the growth rate of the factor independent of k can be polynomial (preferably linear) in the input size, while the factor dependent on k can be relatively small for small values of k (although growing exponentially or even hyper-exponentially.) Problems with this complexity property are called “fixed-parameter tractable” (FPT). Several FPT investigation techniques have been announced and used in research presented at past GROW workshops.

Plenary Speakers
Professor Bruno Courcelle:  LaBRI (Laboratoire Bordelais de Recherche en Informatique), Bordeaux, France.
Professor Zdenek Dvorak:  Computer Science Institute of Charles University, Prague, Czech Republic.
Professor Anna Lubiw:  Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada.

Program and Abstracts