DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.17

Computational Complexity of Matching Match Puzzle

Authors: Yuki Iburi and Ryuhei Uehara

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

Abstract

Various forms of graph coloring problems have been studied over the years in the society of graph theory. Recently, some original puzzles are popularized in Japanese 100-yen shops, and one of them can be formalized as a graph coloring problem in a natural way. However, this natural graph coloring problem has not been investigated in the context of the graph theory. In this paper, we investigate this puzzle as a graph coloring problem. We first prove that this graph coloring problem is NP-complete even when the graph is restricted to a path or a spider. In these cases, diameter of the graphs seems to play an important role for its difficulty. We then show that the problem can be solved in polynomial time when the graph is restricted to some graph classes of constant diameter.

Cite as

Yuki Iburi and Ryuhei Uehara. Computational Complexity of Matching Match Puzzle. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{iburi_et_al:LIPIcs.FUN.2024.17,
  author =	{Iburi, Yuki and Uehara, Ryuhei},
  title =	{{Computational Complexity of Matching Match Puzzle}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{17:1--17:10},
  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.17},
  URN =		{urn:nbn:de:0030-drops-199251},
  doi =		{10.4230/LIPIcs.FUN.2024.17},
  annote =	{Keywords: Graph coloring, Matching Match puzzle, NP-complete, polynomial-time solvable}
}

Search Results

Documents authored by Iburi, Yuki

Computational Complexity of Matching Match Puzzle

Abstract

Cite as

Thanks for your feedback!

Could not send message