- Approximation Algorithms for token swapping on Graphs
- Project Year:
2022
- REU Student (s):
Samuel Hiken | Carleton College MN
- Student 1 Institution:
Carleton College
- Project Mentor:
Nicole Wein
- Project Mentor Area:
DIMACS
- Project Abstract:
Consider the following problem: we are given a graph with $n$ vertices and $n$ distinct tokens. Given two arrangements of the tokens on the vertices, we wish to know the length of the shortest possible sequence of "edge-swaps" needed to get from one arrangement to the other. Here, an edge-swap refers to the act of swapping tokens that lie on adjacent vertices. This problem, known as token swapping, is APX-hard, and a constant-factor approximation has been known since 2016. This summer, I studied the approximability of token swapping on general graphs.
