Top

Published in:

2020 | OriginalPaper | Chapter

On the Parameterized Complexity of Spanning Trees with Small Vertex Covers

Authors : Chamanvir Kaur, Neeldhara Misra

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the minimum power spanning tree (MPST) problem with general and unit demands from a parameterized perspective. The case of unit demands is equivalent to the problem of finding a spanning tree with the smallest possible vertex cover (MCST). We show that MPST is W[1]-hard when parameterized by the vertex cover of the input graph, and is W[2]-hard when parameterized by the solution size—the latter holds even in the case of unit demands. For the special case of unit demands, however, we demonstrate an FPT algorithm when parameterized by treewidth. In the context of kernelization, we show that even MCST is unlikely to admit a polynomial kernel under standard complexity-theoretic assumptions when parameterized by the vertex cover of the input graph.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Parameterized Algorithms for Directed Modular Width

next chapter Minimum Conflict Free Colouring Parameterized by Treewidth

Althaus, E., Călinescu, G., Mandoiu, I.I., Prasad, S.K., Tchervenski, N., Zelikovsky, A.: Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks. Wireless Netw. 12(3), 287–299 (2006)CrossRef

Angel, E., Bampis, E., Chau, V., Kononov, A.: Min-power covering problems. In: Elbassioni, K., Makino, K. (eds.) ISAAC 2015. LNCS, vol. 9472, pp. 367–377. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48971-0_32CrossRef

Angel, E., Bampis, E., Escoffier, B., Lampis, M.: Parameterized power vertex cover. In: Heggernes, P. (ed.) WG 2016. LNCS, vol. 9941, pp. 97–108. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53536-3_9CrossRef

Bonsma, P.S., Zickfeld, F.: Improved bounds for spanning trees with many leaves. Discrete Math. 312(6), 1178–1194 (2012)MathSciNetCrossRef

Calinescu, G., Kortsarz, G., Nutov, Z.: Improved approximation algorithms for minimum power covering problems. In: Epstein, L., Erlebach, T. (eds.) WAOA 2018. LNCS, vol. 11312, pp. 134–148. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04693-4_9CrossRefMATH

Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3CrossRefMATH

Diestel, R.: Graph Theory. GTM, vol. 173. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-53622-3CrossRefMATH

Fukunaga, T., Maehara, T.: Computing a tree having a small vertex cover. In: Chan, T.-H.H., Li, M., Wang, L. (eds.) COCOA 2016. LNCS, vol. 10043, pp. 77–91. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48749-6_6CrossRef

Grandoni, F.: On min-power steiner tree. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 527–538. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_46CrossRef

10.

Ho, J., Lee, D.T., Chang, C., Wong, C.K.: Minimum diameter spanning trees and related problems. SIAM J. Comput. 20(5), 987–997 (1991)MathSciNetCrossRef

11.

Iglesias, J., Rajaraman, R., Ravi, R., Sundaram, R.: Plane gossip: approximating rumor spread in planar graphs. LATIN 2018. LNCS, vol. 10807, pp. 611–624. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77404-6_45CrossRef

12.

Kloks, T. (ed.): Treewidth. LNCS, vol. 842. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0045375CrossRefMATH

Title: On the Parameterized Complexity of Spanning Trees with Small Vertex Covers
Authors: Chamanvir Kaur
Neeldhara Misra
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-030-39218-5

Electronic ISBN: 978-3-030-39219-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39219-2_34

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner