Sunday

15h30-... : Check-in

19h30-22h30: Late dinner (buffet)

Monday

7h30-9h: Breakfast

9h00-10h15: Open problem session I

10h15: Coffee break

10h45-11h45: Tutorial : Reconfiguration and geometry (Anna Lubiw) - Part I

12h: Lunch

14h-15h: Valentin Bartier, Jonathan Noel

15h: Coffee break

15h30-18h: Open problem session II (if needed) AND/OR Work session

19h: Dinner

Tuesday

7h30-9h: Breakfast

9h-10h15: Tutorial: Algorithmic aspects of reconfiguration (Amer Mouawad) - Part I

10h15: Coffee break

10h45-12h: Work session

12h: Lunch

14h-15h: Haruka Mizuta, Vijay Subramanya

15h: Coffee break

15h30-17h45: Work session

18h: Business meeting

19h: Dinner

Wednesday

7h30-9h15: Breakfast

9h15-10h15: Tutorial : Reconfiguration and geometry (Anna Lubiw) - Part II

10h15: Coffee break

10h45-11h45: Carl Feghali, Marc Heinrich

12h: Lunch

13h30: Excursion (Excursion leaders: Benjamin H for the long hike, Feri for the short one)

19h: Aperitives (kir)

19h45: Fondue Dinner

Thursday

7h30-9h: Breakfast

9h-10h15: Tutorial : Algorithmic aspects of reconfiguration (Amer Mouawad) - Part II

10h15: Coffee break

10h45-12h: Work session

12h: Lunch

14h-15h: Richard Brewster, Duc A. Hoang

15h: Coffee break

15h30-18h: Work session

19h: Dinner

Friday

7h30-9h15: Breakfast

9h15-10h15: Nicolas Bousquet, Arnaud Mary

10h15: Coffee break

10h45-11h15: Work session

11h30: Lunch

12h30: Transfer to Modane

Tutorials

Part I.

I will talk about some reconfiguration problems involving discrete planar geometry, starting with the case of non-crossing straight-line spanning trees of points in the plane, and proceeding to triangulations of point sets in the plane. A main theme is to examine reconfiguration problems where the reconfiguration graph is best viewed, not just as a graph, but as the 1-skeleton of a higher dimensional polyhedron or complex. A second theme is the difference between reconfiguration of labelled versus unlabelled elements.

Slides


Part II.

The starting point for this talk is morphing, in particular morphing of planar graph drawings. This is a very continuous type of reconfiguration, but we will view it through the lens of combinatorics. Along the way I will describe the significance for reconfiguration of some classic geometry results, such as Steinitz’s characterization of polyhedral graphs, Tutte’s planar graph drawing algorithm, and Schnyder’s more combinatorial planar graph drawing algorithm. I will also discuss how recent work on hardness for existential theory of the reals is relevant to geometric reconfiguration.

Slides

  • Tutorial 2: Algorithmic Aspects of Reconfiguration: Upper and Lower Bounds (Amer Mouawad) Back to the program

The bulk of algorithms research today is primarily focused on solving static optimization problems, i.e., problems where neither the input nor the solution is expected to change. However, real-life problems typically present themselves in a slightly different form: given the description of a system state and the description of a state that we would “prefer” the system to be in, is it possible to transform the system from its current state into the desired one without “breaking” the system in the process? If possible, what is the “best” way of performing such a transformation? Remarkably, there is currently no established framework for the systematic study of such problems. The research direction which comes closest is the investigation of combinatorial reconfiguration. In this tutorial, we give an overview of some old and new work on reconfiguration problems and discuss tools, results, and future research directions. In particular, the tutorial will cover some of the most widely used techniques in the area for proving both upper and lower algorithmic bounds.

Slides of Part 1 ; Slides of Part 2

Contributed Talks

  • Valentin Bartier. Linear transformations between colorings in chordal graphs Back to the program

(Joint work with Nicolas Bousquet)

Abstract: Let k and d be such that k \ge d+2. Consider two k-colorings of a d-degenerate graph G. Can we transform one into the other by recoloring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. If k=d+2, we know that there exists graphs for which a quadratic number of recolorings is needed. And when k=2d+3, there always exists a linear transformation. In this paper, we prove that, as long as k \ge d+4, there exists a transformation of length at most f(\Delta) * n between any pair of k-colorings of chordal graphs (where \Delta denotes the maximum degree of the graph). The proof is constructive and provides a linear time algorithm that, given two k-colorings computes a linear transformation between them.
Slides

  • Nicolas Bousquet. Graph recoloring: From statistical physics to graph theory Back to the program

Abstract: Sampling (proper) k-colorings of an arbitrary graph received a considerable attention in statistical physics. A (proper) k-coloring is a function that assigns to each vertex an integer between 1 and k, such that, for every edge (u,v) the colors of u and v are different. On way to sample colorings consists in repeating the following random process (Markov chain): given the current coloring, choose a vertex v and a color c at random and recolor v with c if the resulting coloring is proper. Two questions naturally arise: 1) is the chain irreducible (ie is it possible to reach any coloring)? 2) if yes, what is the mixing time of the Markov chain? During this talk we will discuss the relation between these questions and reconfiguration.
Slides

  • Richard Brewster. Reconfiguration of homomorphisms to reflexive digraph cycles Back to the program

Abstract: Let G be a digraph and B be a (fixed) reflexive digraph cycle. Given two homomorphisms phi,phi’ : G -> B, a path from phi to phi” in the Hom-graph Hom(G,B) corresponds to a reconfiguration sequence of the homomorphisms. We give a polynomial time algorithm that either finds a path between two given homomorphisms or discovers an obstruction certifying the non-existence of such a path.
Slides

  • Carl Feghali. Reconfiguring colourings of graphs with bounded maximum average degree Back to the program

Abstract: During this talk, I will sketch a proof of the following result. For every \epsilon > 0 and every graph G with maximum average degree d - \epsilon, R_{d + 1}(G) has diameter O(n (log n)^d).

(Joint work with Nicolas Bousquet)

Abstract: Let k and d be such that k \ge d+2. Consider two k-colourings of a d-degenerate graph G. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length. Cereceda's conjecture can be reformulated as follows: the diameter of the (d+2)-reconfiguration graph of any d-degenerate graph on n vertices is O(n^2). So far, the existence of a polynomial diameter is open even for d=2. We prove that the diameter of the k-reconfiguration graph of a d-degenerate graph is O(n^{d+1}) for k \ge d+2. Moreover, we prove that if k \ge \frac 32 (d+1) then the diameter of the $k$-reconfiguration graph is quadratic, improving the previous bound of $k \ge 2d+1$. We also show that the $5$-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs.
Slides

  • Duc A. Hoang. Shortest Reconfiguration Sequence for Sliding Tokens on Spiders. Back to the program

(Joint work with Amanj Khorramian and Ryuhei Uehara. Accepted at CIAC 2019 (May 27-29, Rome, Italy))

Abstract: Suppose that two independent sets I and J of a graph with |I|=|J| are given, and a token is placed on each vertex in I. The Sliding Token problem is to determine whether there exists a sequence of independent sets which transforms I into J so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. It is one of the representative reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. For a yes-instance of a reconfiguration problem, finding a shortest reconfiguration sequence has a different aspect. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be 𝖭𝖯-hard to find a shortest sequence between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for spiders (i.e., trees having exactly one vertex of degree at least three).
Slides

(Joint work with Jae-Baek Lee and Mark Siggers)

Abstract: A homomorphism from a graph G to a graph H, also called an H-colouring, is a function from V(G) to V(H) such that adjacent vertices of G map to adjacent vertices of H. Homomorphisms can be thought of as a generalisation of proper graph colourings with additional constraints that certain colour patterns are forbidden from appearing on adjacent vertices (e.g. red cannot be adjacent to blue). The reconfiguration problem for H-colourings asks: given a graph G and two H-colourings f and g of G, is it possible to transform f into g by changing the colour of one vertex at a time while always maintaining an H-colouring? In this talk, we will present some recent results on the complexity of this problem which seem to be hinting at interesting connections to other areas such as algebraic topology.
Slides

Abstract: Enumeration problems consist in listing all solutions of a given problem. Since the number of solutions of non trivial problems is often exponential, an algorithm that list all of them cannot run in polynomial time. Among the "tractable" classes of enumeration problems, there is the class of problems that admit a polynomial delay algorithm. We say that an algorithm runs with polynomial delay, if its total running time is poly(n)*N where n is the input size and N is the total number of solutions. In one of the most powerful methods to design polynomial delay algorithms, the correctness of the algorithm is proved by showing that a particular reconfiguration graph is connected. In this talk, we will explain this connection between reconfiguration and enumeration problems and give several examples.
Slides

  • Haruka Mizuta. Reconfiguration of Steiner trees in specific graph classes. Back to the program

Abstract: We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In our study, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.
Slides

Abstract: Under the reconfiguration framework, we consider the various ways that a target graph H is a minor of a host graph G, where a subgraph of G can be transformed into H by means of edge contraction (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an H-model of G is a labeling of the vertices of G with the vertices of H, where the contraction of all edges between identically-labeled vertices results in a graph containing representations of all edges in H. We explore the properties of G and H that result in a connected reconfiguration graph, in which nodes represent H-models and two nodes are adjacent if their corresponding H-models differ by the label of a single vertex of G. Various operations on G or H are shown to preserve connectivity. In addition, we demonstrate properties of graphs G that result in connectivity for the target graphs K_2, K_3, and K_4, including a full characterization of graphs G that result in connectivity for K_2-models, as well as the relationship between connectivity of G and other H-models.
Slides