Document Open Access Logo

An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width

Authors Luisa Gargano, Adele A. Rescigno

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.50.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Luisa Gargano
  • Department of Computer Science, University of Salerno, Italy
Adele A. Rescigno
  • Department of Computer Science, University of Salerno, Italy

Funding

This work was partially supported by project SERICS (PE00000014) under the MUR National Recovery and Resilience Plan funded by the European Union - NextGenerationEU.

Cite As Get BibTex

Luisa Gargano and Adele A. Rescigno. An FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular-Width. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.50

Abstract

The minimum branch vertices spanning tree problem consists in finding a spanning tree T of an input graph G having the minimum number of branch vertices, that is, vertices of degree at least three in T. This NP-hard problem has been widely studied in the literature and has many important applications in network design and optimization. Algorithmic and combinatorial aspects of the problem have been extensively studied and its fixed parameter tractability has been recently considered. In this paper we focus on modular-width and show that the problem of finding a spanning tree with the minimum number of branch vertices is FPT with respect to this parameter.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Graph theory
Keywords
  • Spanning Trees
  • Branch vertices
  • Fixed-parameter tractable algorithms
  • Modular-width

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Baste and D. Watel. An fpt algorithm for node-disjoint subtrees problems parameterized by treewidth. The Computer Journal, 2022. Google Scholar
  2. J.-C. Bermond, L. Gargano, S. Perénnes, A.A. Rescigno, and U. Vaccaro. Optimal time data gathering in wireless networks with multidirectional antennas. Theoretical Computer Science, 509:122-139, 2013. Google Scholar
  3. J.-C. Bermond, L. Gargano, and A.A. Rescigno. Gathering with minimum delay in tree sensor networks. In Proceedings of 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008) Alexander A. Shvartsman and Pascal Felber Eds., Lecture Notes in Computer Science, volume 5058, pages 262-276, 2008. Google Scholar
  4. J.-C. Bermond, L. Gargano, and A.A. Rescigno. Gathering with minimum completion time in sensor tree networks. Journal of Interconnection Networks, 11:1-33, 2010. Google Scholar
  5. F. Carrabs, R. Cerulli, M. Gaudioso, and M. Gentili. Lower and upper bounds for the spanning tree with minimum branch vertices. Computational Optimization and Applications, 56(2):405-438, 2013. Google Scholar
  6. C. Cerrone, R. Cerulli, and A. Raiconi. Relations, models and a memetic approach for three degree-dependent spanning tree problems. European Journal of Operational Research, 232(3):442-453, 2014. Google Scholar
  7. R. Cerulli, M. Gentili, and A. Iossa. Bounded-degree spanning tree problems: models and new algorithms. Computational Optimization and Applications, 42(3):353-370, 2009. Google Scholar
  8. V. M. Chimani and J. Spoerhase. Approximating spanning trees with few branches. Theory of Computing Systems, 56(1):181-196, 2015. Google Scholar
  9. F.V. Fomin, P.A. Golovach, D. Lokshtanov, and S. Saurabh. Clique-width: on the price of general. In Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Claire Mathieu Ed., pages 825-834, 2009. Google Scholar
  10. J. Gajarský, M. Lampis, and S. Ordyniak. Parameterized algorithms for modular-width. In Proceedings of 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), Gregory Gutin and Stefan Szeider Eds., Lecture Notes in Computer Science, volume 8246, pages 163-176, 2013. Google Scholar
  11. L. Gargano, M. Hammar, P. Hell, L. Stacho, and U. Vaccaro. Spanning spiders and light splitting switches. Discrete Mathematics, 285(1):83-95, 2004. Google Scholar
  12. L. Gargano, P. Hell, L.Stacho, and U. Vaccaro. Spanning trees with bounded number of branch vertices. In Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Stephan J. Eidenbenz,Ricardo Conejo, Eds., Lecture Notes in Computer Science, volume 2380, pages 355-365, 2002. Google Scholar
  13. L. Gargano and A. A. Rescigno. Collision-free path coloring with application to minimum-delay gathering in sensor networks. Discrete Applied Mathematics, 157(8):1858-1872, 2009. Google Scholar
  14. L. Gargano and A. A. Rescigno. Complexity of conflict-free colorings of graphs. Theoretical Computer Science, 566:39-49, 2015. Google Scholar
  15. L. Gargano and A. A. Rescigno. Spanning trees with few branch vertices in graphs of bounded neighborhood diversity. In Proceedings of 2023 International Colloquium on Structural Information and Communication Complexity (SIROCCO 2023), Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, Dennis Olivetti Eds., Lecture Notes in Computer Science, volume 13892, pages 502-519, 2023. Google Scholar
  16. D. Gozupek, S. Buhari, and F. Alagoz. A spectrum switching delay-aware scheduling algorithm for centralized cognitive radio networks. IEEE Transactions on Mobile Computing, 12:1270-1280, 2013. Google Scholar
  17. K. Jansen and L. Rohwedderb. On integer programming, discrepancy, and convolution. Mathematics of Operations Research, pages 1-15, 2023. Google Scholar
  18. M. Landete, A. Marín, and J. L. Sainz-Pardo. Decomposition methods based on articulation vertices for degree-dependent spanning tree problems. Computational Optimization and Applications, 68:749-773, 2017. Google Scholar
  19. A. Marin. Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem. European Journal of Operational Research, 245(3):680-689, 2015. Google Scholar
  20. H. Matsuda, K. Ozeki, and T. Yamashita. Spanning trees with a bounded number of branch vertices in a claw-free graph. Graphs and Combinatorics, 30:429-437, 2014. Google Scholar
  21. R. A. Melo, P. Samer, and S. Urrutia. An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices. Computational Optimization and Applications, 65(3):821-844, 2016. Google Scholar
  22. A. Rossi, A. Singh, and S. Shyam. Cutting-plane-based algorithms for two branch vertices related spanning tree problems. Optimization and Engineering, 15:855-887, 2014. Google Scholar
  23. G. Salamon. Spanning tree optimization problems with degree-based objective functions. In Proceedings of 4th Japanese–Hungarian Sym. on Discrete Math. and Its Applications, pages 309-315, 2005. Google Scholar
  24. N. Shami and M. Rasti. A joint multi-channel assignment and power control scheme for energy efficiency in cognitive radio networks. In Proceedings of 2016 IEEE Wireless Communications and Networking Conference (WCNC 2016), pages 1-6, 2016. Google Scholar
  25. R. M. A. Silva, D. M. Silva, M. G. C. Resende, G. R. Mateus, J. F. Gon¸calves, and P. Festa. An edge-swap heuristic for generating spanning trees with minimum number of branch vertices. Optimization Letters, 8(4):1225-1243, 2014. Google Scholar
  26. S. Silvestri, G. Laporte, and R. Cerulli. A branch-and-cut algorithm for the minimum branch vertices spanning tree problem. Comput. Oper. Res., 81:322-332, 2017. Google Scholar
  27. S. Sundar, A. Singh, and A. Rossi. New heuristics for two bounded-degree spanning tree problems. Information Sciences, 195:226-240, 2012. Google Scholar
  28. M. Tedder, D.G. Corneil, M. Habib, and C. Paul. Simpler linear-time modular decomposition via recursive factorizing permutations. In Proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz Eds., Lecture Notes in Computer Science, volume 5125, pages 634-645, 2008. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact