---
_id: '12833'
abstract:
- lang: eng
  text: 'The input to the token swapping problem is a graph with vertices v1, v2,
    . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal
    is to get token i to vertex vi for all i= 1, . . . , n using a minimum number
    of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token
    swapping on a tree, also known as “sorting with a transposition tree,” is not
    known to be in P nor NP-complete. We present some partial results: 1. An optimum
    swap sequence may need to perform a swap on a leaf vertex that has the correct
    token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that
    fixes happy leaves—as all known approximation algorithms for the problem do—has
    approximation factor at least 4/3. Furthermore, the two best-known 2-approximation
    algorithms have approximation factor exactly 2. 3. A generalized problem—weighted
    coloured token swapping—is NP-complete on trees, but solvable in polynomial time
    on paths and stars. In this version, tokens and vertices have colours, and colours
    have weights. The goal is to get every token to a vertex of the same colour, and
    the cost of a swap is the sum of the weights of the two tokens involved.'
acknowledgement: "This work was begun at the University of Waterloo and was partially
  supported by the Natural Sciences and Engineering Council of Canada (NSERC).\r\n"
article_number: '9'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ahmad
  full_name: Biniaz, Ahmad
  last_name: Biniaz
- first_name: Kshitij
  full_name: Jain, Kshitij
  last_name: Jain
- first_name: Anna
  full_name: Lubiw, Anna
  last_name: Lubiw
- first_name: Zuzana
  full_name: Masárová, Zuzana
  id: 45CFE238-F248-11E8-B48F-1D18A9856A87
  last_name: Masárová
  orcid: 0000-0002-6660-1322
- first_name: Tillmann
  full_name: Miltzow, Tillmann
  last_name: Miltzow
- first_name: Debajyoti
  full_name: Mondal, Debajyoti
  last_name: Mondal
- first_name: Anurag Murty
  full_name: Naredla, Anurag Murty
  last_name: Naredla
- first_name: Josef
  full_name: Tkadlec, Josef
  id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
  last_name: Tkadlec
  orcid: 0000-0002-1097-9684
- first_name: Alexi
  full_name: Turcotte, Alexi
  last_name: Turcotte
citation:
  ama: Biniaz A, Jain K, Lubiw A, et al. Token swapping on trees. <i>Discrete Mathematics
    and Theoretical Computer Science</i>. 2023;24(2). doi:<a href="https://doi.org/10.46298/DMTCS.8383">10.46298/DMTCS.8383</a>
  apa: Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., … Turcotte,
    A. (2023). Token swapping on trees. <i>Discrete Mathematics and Theoretical Computer
    Science</i>. EPI Sciences. <a href="https://doi.org/10.46298/DMTCS.8383">https://doi.org/10.46298/DMTCS.8383</a>
  chicago: Biniaz, Ahmad, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow,
    Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, and Alexi Turcotte. “Token
    Swapping on Trees.” <i>Discrete Mathematics and Theoretical Computer Science</i>.
    EPI Sciences, 2023. <a href="https://doi.org/10.46298/DMTCS.8383">https://doi.org/10.46298/DMTCS.8383</a>.
  ieee: A. Biniaz <i>et al.</i>, “Token swapping on trees,” <i>Discrete Mathematics
    and Theoretical Computer Science</i>, vol. 24, no. 2. EPI Sciences, 2023.
  ista: Biniaz A, Jain K, Lubiw A, Masárová Z, Miltzow T, Mondal D, Naredla AM, Tkadlec
    J, Turcotte A. 2023. Token swapping on trees. Discrete Mathematics and Theoretical
    Computer Science. 24(2), 9.
  mla: Biniaz, Ahmad, et al. “Token Swapping on Trees.” <i>Discrete Mathematics and
    Theoretical Computer Science</i>, vol. 24, no. 2, 9, EPI Sciences, 2023, doi:<a
    href="https://doi.org/10.46298/DMTCS.8383">10.46298/DMTCS.8383</a>.
  short: A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla,
    J. Tkadlec, A. Turcotte, Discrete Mathematics and Theoretical Computer Science
    24 (2023).
date_created: 2023-04-16T22:01:08Z
date_published: 2023-01-18T00:00:00Z
date_updated: 2025-01-20T14:05:09Z
day: '18'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
- _id: UlWa
doi: 10.46298/DMTCS.8383
external_id:
  arxiv:
  - '1903.06981'
file:
- access_level: open_access
  checksum: 439102ea4f6e2aeefd7107dfb9ccf532
  content_type: application/pdf
  creator: dernst
  date_created: 2023-04-17T08:10:28Z
  date_updated: 2023-04-17T08:10:28Z
  file_id: '12844'
  file_name: 2022_DMTCS_Biniaz.pdf
  file_size: 2072197
  relation: main_file
  success: 1
file_date_updated: 2023-04-17T08:10:28Z
has_accepted_license: '1'
intvolume: '        24'
issue: '2'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics and Theoretical Computer Science
publication_identifier:
  eissn:
  - 1365-8050
  issn:
  - 1462-7264
publication_status: published
publisher: EPI Sciences
quality_controlled: '1'
related_material:
  record:
  - id: '7950'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Token swapping on trees
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2023'
...