Document Open Access Logo

Linear Transformations Between Dominating Sets in the TAR-Model

Authors Nicolas Bousquet, Alice Joffard, Paul Ouvrard

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.37.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Nicolas Bousquet
  • CNRS, LIRIS, Université de Lyon, Université Claude Bernard Lyon 1, France
Alice Joffard
  • CNRS, LIRIS, Université de Lyon, Université Claude Bernard Lyon 1, France
Paul Ouvrard
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, 33400 Talence, France

Funding

This work was supported by ANR project GrR (ANR-18-CE40-0032).

References

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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. Google Scholar
  7. 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.
  8. 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.
  9. W. Mader. Homomorphiesätze für graphen. Math. Ann., 178:154–168, 1968. Google Scholar
  10. 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.
  11. 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.
  12. 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.
  13. Naomi Nishimura. Introduction to reconfiguration. Algorithms, 11(4):52, 2018. URL: https://doi.org/10.3390/a11040052.
  14. 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.
  15. 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.
  16. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact