Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2017)
Location: Fields Institute, Room 230
** 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 wellknown problemsolving 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 treedecomposition, for which a powerful analytical tool became the concept of a minor (a minimal obstruction set, in general terms.) Treedecomposition lead to the definition of treewidth, one possible parameter describing the complexity of a graph’s parsing. Subsequently, other graphwidth parameters, such as branchwidth and cliquewidth 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 NPhard 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 (NPhard), 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 hyperexponentially.) Problems with this complexity property are called “fixedparameter 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.
Schedule
09:00 to 09:15 
Welcome

09:15 to 10:15 
Bruno Courcelle, Bordeaux University 
10:15 to 10:45 
Coffee Break

10:45 to 11:10 
David Mitchell, Simon Fraser University 
11:10 to 11:35 
Peter Rossmanith, RWTH Aachen University 
11:35 to 12:00 
Dušan Knop, Charles University 
12:00 to 13:30 
Lunch

13:30 to 13:55 
Robert Ganian, Faculty of Informatics, TU Wien 
13:55 to 14:20 
Pierre MEYER, Ecole Normale Supérieure de Lyon 
14:20 to 14:45 
Arash Rafiey, Indiana State University 
14:45 to 15:15 
Coffee Break

15:15 to 15:40 
Martin Milanič, University of Primorska 
15:40 to 16:05 
Laurent Feuilloley, Université Paris Diderot 
16:05 to 16:30 
Peter Zeman, Charles University 
16:30 to 18:00 
Problem Session

19:00 
Banquet  Via Mercanti

09:00 to 09:15 
Announcements

09:15 to 09:40 
Michel Habib, University Paris Diderot 
09:40 to 10:05 
Jesse Beisegel, BTU Cottbus  Senftenberg 
10:05 to 10:30 
Lalla Mouatadid, University of Toronto 
10:30 to 11:00 
Coffee Break

11:00 to 11:25 
Kathie Cameron, Wilfrid Laurier University 
11:25 to 11:50 
Andreas Brandstaedt, University of Rostock 
11:50 to 12:15 
Vaidy Sivaraman, University of Amsterdam 
12:15 to 13:45 
Lunch

13:45 to 14:15 
Humber River Valley hike or other Toronto attractions

09:00 to 09:15 
Announcements

09:15 to 10:15 
Zdenek Dvorak, Charles University in Prague 
10:15 to 10:45 
Coffee Break

10:45 to 11:10 
Chinh Hoang, Wilfrid Laurier University 
11:10 to 11:35 
Yixin Cao, The Hong Kong Polytechnic University 
11:35 to 12:00 
Tomáš Masařík, Charles University 
12:00 to 13:30 
Lunch

13:30 to 13:55 
Sangil Oum, KAIST 
13:55 to 14:20 
ChunHung Liu, Princeton University 
14:20 to 14:45 
Irena Penev, University of Leeds 
14:45 to 15:40 
Coffee Break and bids for GROW2019

15:40 to 16:05 
Christophe Paul, CNRS 
16:05 to 16:30 
George Mertzios, Durham University 
16:30 to 18:00 
Problem Session

09:00 to 09:15 
Announcements

09:15 to 10:15 
Anna Lubiw, University of Waterloo 
10:15 to 10:45 
Coffee Break

10:45 to 11:10 
Iyad Kanj, DePaul University 
11:10 to 11:35 
Steven Chaplick, Universität Würzburg 
11:35 to 12:00 
Till Miltzow, Mathematics 