General Information

---

Project Description

Consider the following problem: we are given a graph G with n vertices, a set of n distinct tokens, and an initial configuration of the tokens on the vertices (with each token placed on a unique vertex). We are also given a target configuration of tokens. Our goal is to find the minimum sequence of "swaps" needed to get from the initial token configuration to the final token configuration, where a swap involves switching the positions of two tokens on adjacent vertices.

This problem, called token swapping, is known to be NP-hard and APX-hard. A 4-approximation was devised in 2016, but we don't know if a better approximation factor is possible. My goal for this summer is to tighten the bounds on approximability of token-swapping, either by devising an algorithm with a lower approximation factor or finding a lower bound on approximability that is strictly greater than 1.

---

Weekly Log

Week 1:

During the first week of the program, I met with my advisor Nicole Wein to talk about token swapping. I read papers by Miltzow et al. [2], Yamanaka et al. [3], and Biniaz et al. [1] on known algorithms for token swapping. On Monday, I gave a presentation on the project to other students in the REU. The only known constant-factor approximation algorithm for token swapping, given by [2], has an approximation factor no worse than 4, but it could be as good as 2. My first goal for this REU is to tighten the bounds on that particular approximation factor.

Week 2:

This week, I was able to demonstrate that the approximation algorithm given by Miltzow et al. in 2016 is not better than a 4-approximation. Moreover, my mentor and I were able to show that a broad class of approximation algorithms also cannot do better than a 4-approximation. This is unfortunate, as there's not an immediately apparent way to come up with an approximation algorithm that does not fall into this class without causing exponential blow-up. In the second half of the week, I started looking into an exact algorithm for complete bipartite graphs. I tried (unsuccessfully) to generalize it to all bipartite graphs. My mentor suspects that the problem is NP-hard on bipartite graphs, and I think she's right.

Week 3:

The only known approximation algorithm for token-swapping on general graphs is a generalization of an algorithm for the problem trees called the 'happy swap algorithm'. This week, I tried generalizing a different approximation algorithm for trees called the 'cycle algorithm.' After not getting much of anywhere with it, I started looking at graphs of bounded treewidth. Treewidth is, informally, a measure of how tree-like a graph is. Given that the approximation algorithm for token-swapping is known to be a 2-approximation on trees (while only a 4-approximation in general), it makes sense to look at what the approximation factor might be on graphs of bounded treewidth.

Week 4:

This week, I continued looking into limited versions of the token-swapping problem. In particular, I spent a long time trying to show that the 2016 approximation algorithm is a 3-approximation on cycles, in the hope that this result can be generalized to all graphs of treewidth 2. The goal is to relate the approximation factor to treewidth. Unfortunately, I was not able to get anywhere. At the end of the week, I read through part of a 2018 paper that gave a reduction to token-swapping from a problem called MULTICOLORED SUBGRAPH ISOMORPHISM. My goal is to modify the reduction to get better bounds on inapproximability [4].

Week 5:

This week, I was able to generalize a 2015 2-approximation for token-swapping on trees given by [3] into a 4-approximation on general graphs. I tried for much of the week to prove that it is better than a 4-approximation, but I wasn't able to get anywhere with it. Later in the week, I returned to the problem of inapproximability. I'm trying to show that some small change in a token-swapping instance can lead to a very large change in the length of the optimal swap sequence, in order to show that an approximation algorithm for token-swapping could allow us to distinguish between yes and no instances of some NP-hard problem.

Week 6:

This week, my mentor and I found that the 4-approximation I developed last week does not actually have an approximation factor better than 4. In fact, for any ε > 0, there exists a cycle for which the approximation factor is worse than 4-ε. That said, the algorithm performs better on instances of token-swapping where the cycles in the cyclic decomposition of the underlying permutation have bounded order. Later in the week, I continued looking at inapproximability bounds for the token-swapping problem. I'm trying a new approach; instead reducing from an NP-hard decision problem, and showing that an approximation algorithm for token-swapping can be used to distinguish between yes and no instances, I'm now trying to reduce from some optimization problem for which we already have inapproximability results.

Week 7:

This week, I finally started making some progress on getting inapproximability bounds for token-swapping. Using a nice reduction from the minimum vertex cover problem (min-VC), I was able to show that weighted token-swapping, a variant of token-swapping introduced by [1], is NP-hard to approximate within a factor of ~1.360-ε, and UG-hard to approximate within a factor of 2-ε for any ε>0. (We prove this by showing that if there exists a polynomial-time α-approximation for weighted token-swapping, there exists a polynomial-time α-approximation for min-VC). In somewhat unrelated news, I was also able to show that the 2016 4-approximation given by [2] is not better than a 4-approximation on planar graphs.

Week 8:

This week, I continued working on getting inapproximability bounds for token-swapping. Using a reduction from min-VC on four-regular graphs, I was able to show that another variant of token-swapping, colored token-swapping, is NP-hard to approximate within a factor of 469/468-ε. I am still working on trying to adapt the approach to get inapproximability bounds for the standard token-swapping problem. I spent most of the last half of the week working on my final presentation and my final REU report.

Another note: at the end of this week, I'm leaving for a combinatorics and graph theory conference in Prague (!), and I'm not sure I'll be able to update this website after I leave Rutgers' campus.

---

Acknowledgements

I am hugely thankful to the DIMACS REU for hosting me this summer. In particular, I'd like to thank Lazaros Gallos for directing the REU and Nicole Wein for serving as my advisor. Furthermore, this research would not be possible without the generous support of the National Science Foundation through grant CNS-2150186.

---

References

[1] Ahmad Biniaz, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. Token Swapping on Trees. 2019

[2] Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness of token swapping. In 24th Annual European Symposium on Algorithms (ESA 2016), LIPIcs-Leibniz International Proceedings in Informatics, volume 57. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016s

[3] Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping labeled tokens on graphs. Theoretical Computer Science, 586:81–94, 2015.

[4] Edouard Bonnet, Tillman Miltzow, Paweł Rzążewski. Complexity of Token-Swapping and its Variants. 2018