DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.5

Swapping Mixed-Up Beers to Keep Them Cool

Authors: Davide Bilò, Maurizio Fiusco, Luciano Gualà, and Stefano Leucci

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

There was a mix-up in Escher’s bar and n customers sitting at the same table have each received a beer ordered by somebody else in the party. The drinks can be rearranged by swapping them in pairs, but the eccentric table shape only allows drinks to be exchanged between people sitting on opposite sides of the table. We study the problem of finding the minimum number of swaps needed so that each customer receives its desired beer before it gets warm. Formally, we consider the Colored Token Swapping problem on complete bipartite graphs. This problem is known to be solvable in polynomial time when all ordered drinks are different [Yamanaka et al., FUN 2014], but no results are known for the more general case in which multiple people in the party can order the same beer. We prove that Colored Token Swapping on complete bipartite graphs is NP-hard and that it is fixed-parameter tractable when parameterized by the number of distinct types of beer served by the bar.

Cite as

Davide Bilò, Maurizio Fiusco, Luciano Gualà, and Stefano Leucci. Swapping Mixed-Up Beers to Keep Them Cool. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.FUN.2024.5,
  author =	{Bil\`{o}, Davide and Fiusco, Maurizio and Gual\`{a}, Luciano and Leucci, Stefano},
  title =	{{Swapping Mixed-Up Beers to Keep Them Cool}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.5},
  URN =		{urn:nbn:de:0030-drops-199132},
  doi =		{10.4230/LIPIcs.FUN.2024.5},
  annote =	{Keywords: Colored Token Swapping, Complete Bipartite Graphs, Labeled Token Swapping, FPT Algorithms, NP-Hardness}
}

Search Results

Documents authored by Fiusco, Maurizio

Swapping Mixed-Up Beers to Keep Them Cool

Abstract

Cite as