CanaDAM 2021
On-line, May 25 - 28, 2021

Invitation to Reconfiguration - Part I
Org: Nicolas Bousquet (CNRS, Université de Lyon) and Anna Lubiw (University of Waterloo)

JEAN CARDINAL, Université Libre de Bruxelles
Flip Distances between Graph Orientations  [PDF]

We consider $\alpha$-orientations of a graph, in which every vertex $v$ has a specified outdegree $\alpha (v)$, and a flip consists of reversing all edges of a directed cycle. We prove that deciding whether the flip distance between two $\alpha$-orientations of a planar graph is at most two is NP-complete. This also holds in the special case of perfect matchings, where flips involve alternating cycles. This problem amounts to finding geodesics on the common base polytope of two partition matroids. We also consider the dual question on graph orientations in which every cycle has a specified number of forward edges.

COLIN R DEFANT & NOAH KRAVITZ, Princeton University
Random Friends and Strangers Walking on Random Graphs  [PDF]

The friends-and-strangers graph $\mathsf{FS}(X,Y)$ associated with $n$-vertex graphs $X$ and $Y$ is a specific graph on the set of bijections $V(X)\to V(Y)$ whose edges are determined by certain local flips. These graphs provide a framework for generalizing transposition Cayley graphs of symmetric groups, the famous $15$-puzzle, generalizations of the $15$-puzzle as studied by Wilson, and work of Stanley related to flag $h$-vectors. We will discuss several results about the number and sizes of the connected components of these friends-and-strangers graphs, with special emphasis on the case where $X$ and $Y$ are Erd\H{o}s--R\'enyi random graphs. Joint work with Noga Alon.

ERIK DEMAINE & NICOLE WEIN, MIT & University of Waterloo
Hardness of Token Swapping on Trees  [PDF]

In the token swapping problem we are given a graph, an initial assignment of one labeled token on each vertex, and a target permutation of the tokens. The goal is to perform the fewest number of swaps to reach the target permutation, where each swap exchanges the two tokens incident to an edge. Token swapping is studied in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. It is known to be NP-hard for general graphs. We study the natural setting where the graph is a tree, and show that token swapping remains NP-hard even for trees.

LINDA KLEIST, Technische Universität Braunschweig
Flip graphs and Rainbow cycles  [PDF]

Flip graphs are fundamental structures associated with families of geometric objects. In a flip graph, vertices correspond to geometric objects and the edges correspond to flip operations which naturally partition into several types. A rainbow cycle is a cycle in which every flip type (color) appears exactly once.

In this talk, we investigate rainbow cycles in a number of flip graphs, i.e., in the flip graph of triangulations, plane trees on point sets, non-crossing perfect matchings on convex point sets, permutations, and k-subsets of [n]. The talk is based on joint work with Stefan Felnser, Torsten Mütze and Leon Sering.

Vertex-Connectivity of Triangulation Flip Graphs of Planar Point Sets  [PDF]

Full triangulations of a finite planar point set $P$ are maximal straight-line embedded plane graphs on $P$. In partial triangulations some non-extreme points can be skipped. Flips are minimal changes in triangulations. They define an adjacency relation on the set of triangulations of $P$, giving rise to the flip graph of all (full or partial) triangulations of $P$. In the seventies Lawson showed that flip graphs are connected.

Our goal is to investigate the structure of flip graphs, with emphasis on their vertex-connectivity. We obtain similar bounds as they follow for regular triangulations from secondary polytopes via Balinski’s Theorem.