LIPIcs.FUN.2018.5.pdf
- Filesize: 0.56 MB
- 13 pages
Document
How Bad is the Freedom to Flood-It?
Authors
Yota Otachi 
-
Part of:
Volume:
9th International Conference on Fun with Algorithms (FUN 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, and Yota Otachi. How Bad is the Freedom to Flood-It?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FUN.2018.5
Abstract
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in Free-Flood-It the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for Fixed-Flood-It become intractable for Free-Flood-It. We also show that some tractable cases for Fixed-Flood-It are still tractable for Free-Flood-It but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for Fixed-Flood-It is always at most twice that of Free-Flood-It, and this is tight.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
- Theory of computation → Parameterized complexity and exact algorithms
Keywords
- flood-filling game
- parameterized complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Raphaël Clifford, Markus Jalsenius, Ashley Montanaro, and Benjamin Sach. The complexity of flood filling games. Theory Comput. Syst., 50(1):72-92, 2012. URL: http://dx.doi.org/10.1007/s00224-011-9339-2.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
- Michael R. Fellows, Uéverton dos Santos Souza, Fábio Protti, and Maise Dantas da Silva. Tractability and hardness of flood-filling games on trees. Theor. Comput. Sci., 576:102-116, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.02.008.
- Michael R. Fellows, Fábio Protti, Frances A. Rosamond, Maise Dantas da Silva, and Uéverton dos Santos Souza. Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number. Discrete Applied Mathematics, 2017. in press. URL: http://dx.doi.org/10.1016/j.dam.2017.07.004.
- Rudolf Fleischer and Gerhard J. Woeginger. An algorithmic analysis of the honey-bee game. Theor. Comput. Sci., 452:75-87, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.05.032.
-
Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006.
- Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno. On complexity of flooding games on graphs with interval representations. In Jin Akiyama, Mikio Kano, and Toshinori Sakai, editors, Computational Geometry and Graphs - Thailand-Japan Joint Conference, TJJCCGG 2012, Bangkok, Thailand, December 6-8, 2012, Revised Selected Papers, volume 8296 of Lecture Notes in Computer Science, pages 73-84. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-45281-9_7.
- Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Gregory Z. Gutin and Stefan Szeider, editors, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, volume 8246 of Lecture Notes in Computer Science, pages 163-176. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03898-8_15.
- Wing-Kai Hon, Ton Kloks, Fu-Hong Liu, Hsiang Hsuan Liu, and Hung-Lung Wang. Flood-it on AT-free graphs. CoRR, abs/1511.01806, 2015. URL: http://arxiv.org/abs/1511.01806.
- Aurélie Lagoutte, Mathilde Noual, and Eric Thierry. Flooding games on graphs. Discrete Applied Mathematics, 164:532-538, 2014. URL: http://dx.doi.org/10.1016/j.dam.2013.09.024.
-
Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012.
- Kitty Meeks and Alexander Scott. The complexity of flood-filling games on graphs. Discrete Applied Mathematics, 160(7-8):959-969, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.09.001.
- Kitty Meeks and Alexander Scott. The complexity of free-flood-it on 2timesn boards. Theor. Comput. Sci., 500:25-43, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.06.010.
- Kitty Meeks and Alexander Scott. Spanning trees and the complexity of flood-filling games. Theory Comput. Syst., 54(4):731-753, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9482-z.
- Kitty Meeks and Dominik K. Vu. Extremal properties of flood-filling games. CoRR, abs/1504.00596, 2015. URL: http://arxiv.org/abs/1504.00596.
- Elad Verbin. Comment to "Is this game NP-Hard? by Sariel Har-Peled. http://sarielhp.org/blog/?p=2005#comment-993, 2009. Accessed: 2018-01-18.
- Uéverton ßdos Santos Souza, Fábio Protti, and Maise Dantas da Silva. An algorithmic analysis of Flood-it and Free-Flood-it on graph powers. Discrete Mathematics & Theoretical Computer Science, 16(3):279-290, 2014. URL: http://dmtcs.episciences.org/2086.