Schedule for: 17w5066 - Combinatorial Reconfiguration

Arriving in Banff, Alberta on Sunday, January 22 and departing Friday January 27, 2017
Sunday, January 22
16:00 - 17:30 Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre)
17:30 - 19:30 Dinner
A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
20:00 - 22:00 Informal gathering (Corbett Hall Lounge (CH 2110))
Monday, January 23
07:00 - 08:45 Breakfast
Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
09:00 - 09:10 Introduction and Welcome by Workshop Organizers (TCPL 202)
09:10 - 10:00 Self-introductions by participants (TCPL 202)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:30 Takehiro Ito: Invitation to Combinatorial Reconfiguration (TCPL 202)
11:30 - 13:00 Lunch (Vistas Dining Room)
13:10 - 14:10 Guided Tour of The Banff Centre
Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.
(Corbett Hall Lounge (CH 2110))
14:20 - 14:50 Henning Fernau: Open problem (TCPL 202)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 15:50 Tatsuhiko Hatanaka: Open problem - Optimizing a Coloring via a Reconfiguration Sequence (TCPL 202)
15:50 - 16:10 Jan van den Heuvel: Open problem (TCPL 202)
16:10 - 17:30 Follow-up discussion on open problems (TCPL 202)
17:30 - 19:30 Dinner
A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.
(Vistas Dining Room)
Tuesday, January 24
07:00 - 08:50 Breakfast (Vistas Dining Room)
08:50 - 09:05 Introduction and Welcome by BIRS Station Manager (TCPL 201)
09:05 - 09:35 Nicolas Bousquet: Token Sliding on chordal graphs
Let $I$ be an independent set of a graph $G$. Imagine that a token is located on any vertex of $I$. We can now move the tokens of $I$ along the edges of the graph as long as the set of tokens still defines an independent set of $G$. Given two independent sets $I$ and $J$, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms $I$ into $J$ so that every pair of consecutive independent sets of the sequence can be obtained via a token move. This problem is known to be PSPACE-complete even on planar graphs. Demaine et al. [ISAAC'14] asked whether the Token Sliding reconfiguration problem is polynomial time solvable on interval graphs and more generally in chordal graphs. Yamada and Uehara [WALCOM'16] showed that a polynomial time transformation can be found in proper interval graphs. We answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether two independent sets of an interval graph are in the same connected component. Moreover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of $k$-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs.
(TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:50 - 11:10 Nicolas Bousquet: Open problem - Graph recoloring on sparse classes of graphs
Two proper $k$-colorings of $G$ are incident if they differ on exactly one color. We can define the $k$-reconfiguration graph of $G$ where the vertices are the proper $k$-colorings of $G$ and we create an edge between two colorings if they are incident. One of the main conjectures in the reconfiguration community is the one by Cereceda, stating the following: for any $k$-degenerate graph $G$, the diameter of the $(k+2)$-reconfiguration graph of $G$ is quadratic in $|G|$. We will discuss partial results, generalization and open problems related to this conjecture.
(TCPL 201)
11:10 - 11:30 Follow-up discussion on open problems (TCPL 201)
11:30 - 13:30 Lunch (Vistas Dining Room)
13:30 - 13:50 Kunihiro Wasa: Open problem (TCPL 202)
14:00 - 14:20 Group Photo
Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!
(TCPL Foyer)
14:20 - 14:40 Ryuhei Uehara: Open problem (TCPL 202)
14:40 - 15:00 Follow-up discussion on open problems (TCPL 202)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:30 Follow-up discussion on open problems (TCPL 202)
17:30 - 19:30 Dinner (Vistas Dining Room)
Wednesday, January 25
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 09:30 Akira Suzuki: Reduction Tools on NCL (TCPL 201)
09:30 - 10:00 Follow-up discussion (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Karen Seyffarth (TCPL 201)
11:00 - 11:30 Matthew Johnson: Kempe Equivalence in Regular Graphs (TCPL 201)
11:30 - 13:30 Lunch (Vistas Dining Room)
13:30 - 17:30 Free Afternoon (Banff National Park)
17:30 - 19:30 Dinner (Vistas Dining Room)
Thursday, January 26
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Business meeting (TCPL 201)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:00 Jan van den Heuvel: Token-sliding problems (TCPL 201)
11:00 - 11:30 Follow-up discussion (TCPL 201)
11:30 - 13:30 Lunch (Vistas Dining Room)
13:30 - 14:00 Moritz Muehlenthaler: Reconfiguration in Matroids Revisited (TCPL 201)
14:00 - 14:30 Ruth Haas (TCPL 201)
14:30 - 15:00 Follow-up discussion (TCPL 201)
15:00 - 15:30 Coffee Break (TCPL Foyer)
15:30 - 17:30 Follow-up discussion (TCPL 201)
17:30 - 19:30 Dinner (Vistas Dining Room)
Friday, January 27
07:00 - 09:00 Breakfast (Vistas Dining Room)
09:00 - 10:00 Follow-up discussion (TCPL 202)
10:00 - 10:30 Coffee Break (TCPL Foyer)
10:30 - 11:30 Follow-up discussion (TCPL 202)
11:30 - 12:00 Checkout by Noon
5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.
(Front Desk - Professional Development Centre)
12:00 - 13:30 Lunch from 11:30 to 13:30 (Vistas Dining Room)