The First Workshop on
Development of Algorithmic Techniques for Combinatorial Reconfiguration

(Kick-off meeting of the DATCORE project)

July 16-21, 2018, Lyon, France


Combinatorial reconfiguration asks the reachability/connectivity of the solution space formed by feasible solutions of a combinatorial (search) problem. This workshop aims to develop new algorithmic techniques for combinatorial reconfiguration. To this end, the workshop offers an opportunity to share recent results on reconfiguration and its related topics, and to work on open problems. This workshop is organized by the DATCORE project with the support of Sakura program between France and Japan by MAEDI (France) and JSPS (Japan).

Venue.

The workshop will be held on the campus of University Lyon 1, La Doua in the CS lab building called "Nautibus" (see map below).
Two rooms in the Nautibus building have been booked for the whole week, TD12 and TD13. All the presentation will occur in TD12. For working or discussion sessions, we have booked a second room. We may split into several groups (according to their interests) that work in the two adjacent rooms TD12 and 13. These two rooms are in the first floor.

Registration Fee.

Free of charge.

Confirmed Participants.

If you want to participate, please contact Nicolas Bousquet and/or Takehiro Ito.

Program.

We are now calling for a short talk (about 20 minutes) on some of your results related to reconfiguration. Please send a title and an abstract to Nicolas Bousquet and Takehiro Ito before June 29.
We are also planning to have a lot of time to work on open problems together. If you have an open question to work together, please send its short summary to Nicolas Bousquet and Takehiro Ito (preferably, before the workshop).

As a social event, we will go for a dinner together on the Wednesday evening (your own charge).

Tentative program

The first day morning, July 16, the welcome will start at 9h30 at the room TD12 in the Nautibus building. A short self-introductions of the participants will follow when all the members will be there (around 10 AM). Our program is basically flexible so that we can enjoy intensive discussions without annoying at the time. As triggers for our discussions, the following talks are planned. (Just as rough standard, each speaker is expected to talk about 20-minuts, but longer or shorter talks are welcome if you wish more time !) The remaining time (in particular, the second half of the week) is devoted to work on open problems together. We may split into several working groups according to their interests; in that case, we will give some information on our progress to the other working groups at the end of each day.
Open problems sessions are planned on Monday and Tuesday afternoon.
As a social event, we will go for a dinner together on the Wednesday evening (your own charge).


Transportation.

The workshop will be organized on the campus of University Lyon 1, La Doua in the CS lab building called "Nautibus". The best way to go to Nautibus building is to take the tramway T1 or T4. You can take the tranway T1 in front of the rail station or the tramway T4 just behind it. You have to leave the tramway at station "Universite Lyon 1". The Nautibus building is 2 minutes walk from the station (see a google map for the precise location). You can find all the information you need on the public transportation in Lyon on the website of TCL (such as timetables, planning of your trip...etc...).
To go to or come from the airport of Lyon to the Gare Part Dieu railstation the simplest way consists in taking the RhoneExpress tramway. It is convenient even though quite expansive. You can buy your tickets at the airport or online on their website.

Abstracts:

Marthe Bonamy: Distributed Recoloring.

GIven two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously.
We are interested in the following questions: How many communication rounds are needed (in the LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier?
The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids.
(This is joint work with Paul Ouvrard, Mikaël Rabie, Jukka Suomela and Jara Uitto.)



Nicolas Bousquet: Token jumping in K_ll-free graphs.

Given two k-independent sets I and J of a graph G, one can ask if it is possible to transform the one into the other in such a way that, at any step, we replace one vertex of the current independent set by another while keeping the property of being independent. Deciding this problem, known as the Token Jumping (TJ) reconfiguration problem, is PSPACE-complete even on planar graphs. Ito et al. proved in 2014 that the problem is FPT parameterized by k if the input graph is K_3,l-free. We prove that the result of Ito et al. can be extended to any K_l,l-free graphs. As a by product, the TJ-reconfiguration problem is FPT in many well-known classes of graphs such as any minor-free class.
(Joint work with Arnaud Mary and Aline Parreau.)



Marc Heinrich: Random edge colorings using reconfiguration.

The usual reconfiguration operation on (vertex) colorings of a graph consists in selecting a single vertex, and changing its color to a new color not present in its neighborhood. We study the effect of repeatedly applying a random transformation starting from an arbitrary coloring. Standard result from Markov chain theory state that, if the reconfiguration graph is connected, the process converges to a random coloring chosen uniformly at random among all possible colorings of the graph. A question that has attracted some attention in the literature asks 'how fast does the coloring converges to a uniform one'. It is well known that $Delta+2$ colors are enough for the reconfiguration graph to be connected, and a conjecture from Vigoda state that this number of colors is also enough for the process to converge fast. It was proved that $2\Delta$ colors are enough to get a small mixing time. This was later improved to 11/6, and several results were obtained for particular classes of graphs. We study this problem in the case of edge coloring trees.
(This is joint work with Guillem Perarnau and Michelle Delcourt.)



Arnaud Mary: Reconfiguration of graphs realizing a given degree sequence with connectivity constraints.

A graph G realizes the degree sequence S if the degrees of its vertices in the non increasing order is S. Hakimi gave a necessary and sufficient condition to guarantee that there exists a connected multigraph realizing S. Taylor later proved that all the connected multigraphs can be obtained from any of them via a sequence of flips. A flip consists in replacing two edges ab, cd by the diagonals ac and bd. In this paper, we study a generalization of this problem. We are interested in multigraphs realizing a degree sequence S and such that the graphs induced by some given subsets of vertices are connected. Such constraints naturally appear in tandem mass spectrometry.
We show that it is possible to decide in polynomial if there exists a graph realizing S and satisfying the connectivity constraints. Moreover, we prove that the reconfiguration graph given by the flip operation is connected. The proof provides an upper bound on the diameter of the reconfiguration graph and an approximation algorithm for the shortest transformation whose ratio depends on the structure of the subsets of vertices that define the connectivity constraints.
(Joint work with Nicolas Bousquet)



Moritz Muhlenthaler: Shortest reconfiguration of Matchings

Imagine that unlabelled tokens are placed on the edges forming a matching of a graph. A token can be moved to another edge, if the edges containing tokens remain a matching. Then, the distance between two configurations of tokens is the minimum number of moves required to trans- form one into the other. In this paper, we study the problem of computing the distance between two given configurations. We prove that the problem can be solved in polynomial time if the corresponding matchings are not inclusion-wise maximal, and otherwise it admits no polynomial- time sublogarithmic-factor approximation algorithm unless P = NP. Furthermore, we show that for maximum-cardinality matchings of bipartite graphs, the problem is fixed-parameter tractable when parameterized by the size d of the symmetric difference of two given configurations, and obtain a d^ε -factor approximation algorithm for every ε > 0. Finally, we show that determining the (exact) distance between two configurations is complete for the class D^P , and determining the maximum distance between any two configurations of a given graph is D^P -hard.
(Joint work with Nicolas Bousquet, Tatsuhiko Hatanaka and Takehiro Ito)



Paul Ouvrard: Dominating sets reconfiguration under token sliding

Abstract : Let $G$ be a graph and $D_s$ and $D_t$ be two dominating sets of $G$ of size $k$. We want to know if there exists a sequence of dominating sets of $G$ $< D_1 = D_s, D_2, \cdots, D_i = D_t >$ such that $D_{i+1}$ can be obtained from $D_i$ by switching exactly one vertex with one of its neighbors. In this talk, we investigate the complexity of this decision problem. More precisely, we prove that this problem remains PSPACE-complete, even when restricted to split graphs for instance. On the other hand, we present a polynomial-time algorithm for dually chordal graphs.
Joint work with Marthe Bonamy and Paul Dorbec.