Life at Fields
GROW: Workshop
on Graph Classes,
Optimization, and Width
Parameters
MANY PRACTICAL PROBLEMS in applied computer sci-
ence can be modelled by a mathematical structure called a
graph or network. Most of these problems, often expressed
in an optimization framework – find the largest complete sub-
graph, find the shortest spanning tour, find the minimum parti-
tion into independent sets – are intractable in the sense that
it is very unlikely that a polynomial time algorithm exists. A
large fraction of theoretical computer science research deals
with such complexity issues. Intractability properties such as
NP-hardness necessitate novel theoretical and practical ad-
vances – such as determining some underlying structure in
the data – to find efficient, heuristic solutions to real world
problems.
The first GROW (Workshop on Graph Classes, Optimization,
and Width Parameters) was held in Barcelona, Spain in 2001
as a conference of mathematicians and computer scientists
engaged in cutting-edge research in the area of discrete
optimization algorithms on graphs. At the second GROW
in Prague, Czech Republic, in 2005, it was agreed that the
workshop would become a biennial event. This year’s event
was held at the Fields Institute in Toronto.
A list of open
problems presented
at GROW 2017
is posted on the
workshop website.
As with other GROW workshops, GROW 2017 had both in-
vited (Bruno Courcelle, Zdenek Dvorak, and Anna Lubiw) and
contributed talks as well as problem solving or discussion
sessions. Thus, the researchers had a forum to share and
discuss interesting and important applications, problems, and
solution methods, which inevitably resulted in the establish-
ment of many new research collaborations. This is especially
rewarding for young scientists.
After each workshop, full versions of selected papers are in-
vited to a special issue of the journal Discrete Applied Math-
ematics. Andrzej Proskurowski will be the Editor in Chief of
the DAM issue associated with GROW 2017. It has been an
important tradition, and an indication of the interest among
research groups in the themes of our workshops, that some
open problems discussed during the workshop are often
solved in subsequent special issues.
GROW 2017 also greatly benefited from the serendipitous
Tuesday, October 12th timing of Dr. Robert Tarjan's lecture
on "Concurrent Disjoint Set Union" as part of U of T's Depart-
ment of Computer Science Distinguished Lecture Series.
From the beginning, GROW has
been run as an academic, grass-
roots directed event with no af-
filiation with any formal organiza-
tion. Furthermore, the workshop
is invitation only with considerable
emphasis spent on identifying new
junior colleagues interested in the
GROW areas. Through GROW, we
hope to unite theory and practice by
demonstrating how graph-theoretic
concepts can be applied to various
areas in computer science, and by
extracting new application-motivat-
ed problems.
— Derek G. Corneil
8