# Workshop on Graph Classes, Optimization, and Width Parameters (GROW 2017)

October 10 - 13, 2017, The Fields Institute

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.

## Schedule

09:00 to 09:15 | Welcome |

09:15 to 10:15 |
Tree-width, clique-width and fly-automata
Bruno Courcelle, Bordeaux University |

10:15 to 10:45 | Coffee Break |

10:45 to 11:10 |
Graph Width and Practical Existential Second Order Model Checking.
David Mitchell, Simon Fraser University |

11:10 to 11:35 |
Efficient FO-Model Checking on Preferential Attachement Graphs
Peter Rossmanith, RWTH Aachen University |

11:35 to 12:00 |
Combinatorial n-fold Integer Programming and Applications
Dušan Knop, Charles University |

12:00 to 13:30 | Lunch |

13:30 to 13:55 |
On Structural Paramerizations of the Edge Disjoint Paths Problem
Robert Ganian, Faculty of Informatics, TU Wien |

13:55 to 14:20 |
Kernelization algorithms for some link stream editing problems
Pierre MEYER, Ecole Normale Supérieure de Lyon |

14:20 to 14:45 |
Digraph Classes and Homomorphism Problems
Arash Rafiey, Indiana State University |

14:45 to 15:15 | Coffee Break |

15:15 to 15:40 |
Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity
Martin Milanič, University of Primorska |

15:40 to 16:05 |
Graph classes defined via vertex orderings avoiding patterns
Laurent Feuilloley, Université Paris Diderot |

16:05 to 16:30 |
On $H$-topological intersection graphs
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 |
A new graph parameter to measure linearity
Michel Habib, University Paris Diderot |

09:40 to 10:05 |
AT-free BFS Orders
Jesse Beisegel, BTU Cottbus - Senftenberg |

10:05 to 10:30 |
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Lalla Mouatadid, University of Toronto |

10:30 to 11:00 | Coffee Break |

11:00 to 11:25 |
Solving Colouring and Max Weight Stable Set on (Cap, Even Hole)-Free Graphs
Kathie Cameron, Wilfrid Laurier University |

11:25 to 11:50 |
On Efficient Domination for Some Classes of $H$-Free Chordal Graphs
Andreas Brandstaedt, University of Rostock |

11:50 to 12:15 |
Three graph classes: mock threshold, cute, and nice graphs
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 |
Structure of critical graphs and complexity of coloring
Zdenek Dvorak, Charles University in Prague |

10:15 to 10:45 | Coffee Break |

10:45 to 11:10 |
On the structure of graphs without odd or even holes
Chinh Hoang, Wilfrid Laurier University |

11:10 to 11:35 |
Unit Interval Vertex Deletion: Fewer Vertices are Relevant
Yixin Cao, The Hong Kong Polytechnic University |

11:35 to 12:00 |
Parameterized complexity of metatheorems of fair deletion problems
Tomáš Masařík, Charles University |

12:00 to 13:30 | Lunch |

13:30 to 13:55 |
Chi-boundedness of graph classes excluding wheel vertex-minors
Sang-il Oum, KAIST |

13:55 to 14:20 |
Half-integral Erdos-Posa property for topological minors
Chun-Hung Liu, Princeton University |

14:20 to 14:45 |
Clique-cutsets beyond chordal graphs
Irena Penev, University of Leeds |

14:45 to 15:40 | Coffee Break and bids for GROW2019 |

15:40 to 16:05 |
Connected search against a lazy robber and connected treewidth
Christophe Paul, CNRS |

16:05 to 16:30 |
Algorithms and Complexity on Temporal Graphs
George Mertzios, Durham University |

16:30 to 18:00 | Problem Session |

09:00 to 09:15 | Announcements |

09:15 to 10:15 |
Morphing and Compatible Triangulations of Planar Graph Drawings
Anna Lubiw, University of Waterloo |

10:15 to 10:45 | Coffee Break |

10:45 to 11:10 |
How to navigate a robot through obstacles?
Iyad Kanj, DePaul University |

11:10 to 11:35 |
Beyond Outerplanarity
Steven Chaplick, Universität Würzburg |

11:35 to 12:00 |
Fine-grained complexity of coloring unit disks
Till Miltzow, MATHEMATICS |