Development of Algorithmic Techniques for Combinatorial Reconfiguration

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).

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 TD13. These two rooms are in the first floor.

- Alexandre Blanché
- Marthe Bonamy
- Nicolas Bousquet (scientific organizer, local organizer)
- Marc Heinrich (local organizer)
- Takehiro Ito (scientific organizer)
- Yusuke Kobayashi
- Arnaud Mary
- Haruka Mizuta
- Moritz Mühlenthaler
- Paul Ouvrard
- Aline Parreau (local organizer)
- Akira Suzuki
- Kunihiro Wasa

Open problems sessions are planned on Monday and Tuesday afternoon.

**July 16 (Monday) morning, from 10h30**- Nicolas Bousquet: Token Jumping on K_ll-free graphs.
- Kunihiro Wasa: Efficient enumeration of bipartite subgraphs in graphs.

**July 16 (Monday) afternoon, from 13h45**- Akira Suzuki: On the dominating set reconfiguration problem.
- Paul Ouvrard: Dominating sets reconfiguration under token sliding.

**July 17 (Tuesday) from 9h15**- Marc Heinrich: Random edge colorings using reconfiguration.
- Takehiro Ito: Reconfiguration of colorable sets in classes of perfect graphs.
- Haruka Mizuta: Reconfiguring spanning and induced subgraphs.
- Marthe Bonamy: Distributed Recoloring.

**July 18 (Wednesday) from 9h15**- Arnaud Mary: Reconfiguration of graphs realizing a given degree sequence with connectivity constraints.
- Yusuke Kobayashi: Reconfiguration of maximum-weight b-matchings in a graph.
- Moritz Mühlenthaler: Shortest reconfiguration of matchings.

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.

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, Mikael 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.