LIPIcs.ISAAC.2020.37.pdf
- Filesize: 0.57 MB
- 14 pages
Document
Linear Transformations Between Dominating Sets in the TAR-Model
Authors
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
Cite AsGet BibTex
Nicolas Bousquet, Alice Joffard, and Paul Ouvrard. Linear Transformations Between Dominating Sets in the TAR-Model. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.37
https://doi.org/10.4230/LIPIcs.ISAAC.2020.37
Abstract
Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = ⟨ D₀ = D_s, D₁ …, D_𝓁 = D_t ⟩ of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k.
We first improve a result of Haas and Seyffarth [R. Haas and K. Seyffarth, 2017], by showing that if k = Γ(G)+α(G)-1 (where Γ(G) is the maximum size of a minimal dominating set and α(G) the maximum size of an independent set), then there exists a linear TAR reconfiguration sequence between any pair of dominating sets.
We then improve these results on several graph classes by showing that the same holds for K_𝓁-minor free graph as long as k ≥ Γ(G)+O(𝓁 √(log 𝓁)) and for planar graphs whenever k ≥ Γ(G)+3. Finally, we show that if k = Γ(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
Keywords
- reconfiguration
- dominating sets
- addition removal
- connectivity
- diameter
- minor
- treewidth
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alexandre Blanché, Haruka Mizuta, Paul Ouvrard, and Akira Suzuki. Decremental optimization of dominating sets under the reconfiguration framework. In Lecture Notes in Computer Science, pages 69-82. Springer International Publishing, 2020. URL: https://doi.org/10.1007/978-3-030-48966-3_6.
- Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305-1317, December 1996. URL: https://doi.org/10.1137/s0097539793251219.
- R. Haas and K. Seyffarth. The k-dominating graph. Graphs and Combinatorics, 30(3):609-617, March 2013. URL: https://doi.org/10.1007/s00373-013-1302-3.
- R. Haas and K. Seyffarth. Reconfiguring dominating sets in some well-covered and other classes of graphs. Discrete Mathematics, 340(8):1802-1817, 2017. URL: https://doi.org/10.1016/j.disc.2017.03.007.
- Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, and Youcef Tebbal. The complexity of dominating set reconfiguration. Theoretical Computer Science, 651:37-49, October 2016. URL: https://doi.org/10.1016/j.tcs.2016.08.016.
-
T. Ito, E.D. Demaine, N.J.A. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara, and Y. Uno. On the complexity of reconfiguration problems. Theoretical Computer Science, 412(12-14):1054-1065, 2011.
- Takehiro Ito, Haruka Mizuta, Naomi Nishimura, and Akira Suzuki. Incremental optimization of independent sets under the reconfiguration framework. In Lecture Notes in Computer Science, pages 313-324. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_26.
- Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.S. Ramanujan, and Saket Saurabh. Reconfiguration on sparse graphs. Journal of Computer and System Sciences, 95:122-131, August 2018. URL: https://doi.org/10.1016/j.jcss.2018.02.004.
-
W. Mader. Homomorphiesätze für graphen. Math. Ann., 178:154–168, 1968.
- Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. Algorithmica, 78(1):274-297, May 2016. URL: https://doi.org/10.1007/s00453-016-0159-2.
- C. M. Mynhardt and S. Nasserasr. Reconfiguration of colourings and dominating sets in graphs. In 50 Years of Combinatorics, Graph Theory, and Computing, pages 171-191. Chapman and Hall/CRC, November 2019. URL: https://doi.org/10.1201/9780429280092-10.
- C.M. Mynhardt, L.E. Teshima, and A. Roux. Connected k-dominating graphs. Discrete Mathematics, 342(1):145-151, January 2019. URL: https://doi.org/10.1016/j.disc.2018.09.006.
- Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
- Akira Suzuki, Amer E. Mouawad, and Naomi Nishimura. Reconfiguration of dominating sets. Journal of Combinatorial Optimization, 32(4):1182-1195, August 2015. URL: https://doi.org/10.1007/s10878-015-9947-x.
- Andrew Thomason. An extremal function for contractions of graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 95(2):261–265, 1984. URL: https://doi.org/10.1017/S0305004100061521.
-
Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors, Surveys in Combinatorics, volume 409 of London Mathematical Society Lecture Note Series, pages 127-160. Cambridge University Press, 2013.