Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Exact and Parameterized Algorithms for Max Internal Spanning Tree

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the \(\mathcal{NP}\)-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form \(\mathcal{O}^{*}(c^{n})\) with c≤2. For graphs with bounded degree, c<2. The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of \(\mathcal{O}(1.8612^{n})\) when analyzed with respect to the number of vertices. We also show that its running time is \(2.1364^{k} n^{\mathcal{O}(1)}\) when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1–3), 21–46 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bellman, R.: Dynamic programming treatment of the Travelling Salesman Problem. J. Assoc. Comput. Mach. 9, 61–63 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  3. Binkele-Raible, D.: Amortized analysis of exponential time- and parameterized algorithms: Measure & Conquer and Reference Search Trees. Ph.D. Thesis, Universität Trier, Germany (2010)

  4. Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the 2n-barrier for Irredundance: two lines of attack. J. Discrete Algorithms 9, 214–230 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  5. Binkele-Raible, D., Fernau, H.: Enumerate and measure, improving parameter budget management. In: Parameterized and Exact Computation, IPEC. Lecture Notes in Computer Science, vol. 6478, pp. 38–49. Springer, Berlin (2010). Long version accepted to be published in Algorithmica under the title “Parameterized Measure & Conquer for problems with no small kernels.”

    Chapter  Google Scholar 

  6. Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbius: fast subset convolution. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, STOC, pp. 67–74. ACM, New York (2007)

    Google Scholar 

  7. Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The Travelling Salesman Problem in bounded degree graphs. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) In: Proceedings of 35th International Colloquium on Automata, Languages and Programming, ICALP, Part I: Tack A: Algorithms, Automata, Complexity, and Games. Lecture Notes in Computer Science, vol. 5125, pp. 198–209. Springer, Berlin (2008)

    Google Scholar 

  8. Björklund, A.: Determinant sums for undirected Hamiltonicity. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 173–182. IEEE Comput. Soc., Los Alamitos (2010)

    Chapter  Google Scholar 

  9. Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41, 280–301 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40–42), 3736–3756 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Cohen, N., Fomin, F.V., Gutin, G., Kim, E.J., Saurabh, S., Yeo, A.: Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem. J. Comput. Syst. Sci. 76(7), 650–662 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Eppstein, D.: The Traveling Salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61–81 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fellows, M.R.: Towards fully multivariate algorithmics: some new results and directions in parameter ecology. In: Fiala, J., Kratochvíl, J., Miller, M. (eds.) Combinatorial Algorithms, 20th International Workshop, IWOCA. Lecture Notes in Computer Science, vol. 5874, pp. 2–10. Springer, Berlin (2009)

    Google Scholar 

  14. Fernau, H., Gaspers, S., Raible, D.: Exact and parameterized algorithms for max internal spanning tree. In: Paul, C., Habib, M. (eds.) Graph-Theoretic Concepts in Computer Science, 35th International Workshop, WG. Lecture Notes in Computer Science, vol. 5911, pp. 100–111. Springer, Berlin (2010)

    Chapter  Google Scholar 

  15. Fernau, H., Gaspers, S., Raible, D., Stepanov, A.A.: Exact exponential time algorithms for Max Internal Spanning Tree. arxiv:0811.1875 (2008)

  16. Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Raible, D., Rossmanith, P.: An exact algorithm for the Maximum Leaf Spanning Tree problem. In: Chen, J., Fomin, F.V. (eds.) Proceedings of 4th International Workshop on Parameterized and Exact Computation, IWPEC. Lecture Notes in Computer Science, vol. 5917, pp. 161–172. Springer, Berlin (2009). Long version to appear in Theor. Comput. Sci.

    Chapter  Google Scholar 

  17. Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the Minimum Feedback Vertex Set problem: exact and enumeration algorithms. Algorithmica 52(2), 293–307 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Fomin, F.V., Gaspers, S., Saurabh, S., Thomassé, S.: A linear vertex kernel for Maximum Internal Spanning Tree. In: Dong, Y., Du, D.-Z., Ibarra, O.H. (eds.) Algorithms and Computation, 20th International Symposium, ISAAC, Lecture Notes in Computer Science, vol. 5878, pp. 267–277. Springer, Berlin (2009)

    Google Scholar 

  19. Fomin, F.V., Grandoni, F., Kratsch, D.: A Measure & Conquer approach for the analysis of exact algorithms. Journal of the Association for Computing Machinery 56(5) (2009)

  20. Fomin, F.V., Grandoni, F., Kratsch, D.: Solving Connected Dominating Set faster than 2n. Algorithmica 52(2), 153–166 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  21. Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  22. Fomin, F.V., Lokshtanov, D., Grandoni, F., Saurabh, S.: Sharp separation and applications to exact and parameterized algorithms. In: López-Ortiz, A. (ed.) Proceedings of LATIN, 9th Latin American Theoretical Informatics Symposium. Lecture Notes in Computer Science, vol. 6034, pp. 72–83. Springer, Berlin (2010)

    Google Scholar 

  23. Gaspers, S.: Exponential time algorithms: structures, measures, and bounds. Ph.D. Thesis, University of Bergen (2008)

  24. Gaspers, S., Saurabh, S., Stepanov, A.A.: A moderately exponential time algorithm for Full Degree Spanning Tree. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) Proceedings of TAMC, Theory and Applications of Models of Computation, 5th International Conference. Lecture Notes in Computer Science, vol. 4978, pp. 479–489. Springer, Berlin (2008)

    Google Scholar 

  25. Gaspers, S., Sorkin, G.B.: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. In Mathieu, C. (ed.) Proceedings of SODA, 20th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, pp. 606–615 (2009). Long version accepted to be published in J. Comput. Syst. Sci.

    Google Scholar 

  26. Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10, 196–210 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  27. Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) Proceedings of 13th Annual International Conference, Computing and Combinatorics, COCOON. Lecture Notes in Computer Science, vol. 4598, pp. 108–117. Springer, Berlin (2007)

    Google Scholar 

  28. Karp, R.M.: Dynamic programming meets the principle of inclusion-exclusion. Inf. Process. Lett. 1(2), 49–51 (1982)

    MathSciNet  MATH  Google Scholar 

  29. Knauer, M., Spoerhase, J.: Better approximation algorithms for the Maximum Internal Spanning Tree Problem. In: Dehne, F.K.H.A., Gavrilova, M.L., Sack, J.-R., Tóth, C.D. (eds.) Proceedings of WADS, Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 5664, pp. 459–470. Springer, Berlin (2009)

    Google Scholar 

  30. Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the Traveling Salesman Problem. In: Proceedings of the 1977 ACM Annual Conference, pp. 294–300. ACM, New York (1977)

    Chapter  Google Scholar 

  31. Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Schulman, L.J. (ed.) Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pp. 321–330. ACM, New York (2010)

    Chapter  Google Scholar 

  32. Lokshtanov, D., Saurabh, S.: Even faster algorithm for Set Splitting! In: Chen, J., Fomin, F.V. (eds.) Proceedings of Parameterized and Exact Computation, 4th International Workshop, IWPEC. Lecture Notes in Computer Science, vol. 5917, pp. 288–299. Springer, Berlin (2009)

    Chapter  Google Scholar 

  33. Mays, L.M.: Water Resources Engineering, 2nd edn. Wiley, New York (2010)

    Google Scholar 

  34. Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23–28 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  35. Nederlof, J.: Fast polynomial-space algorithms using Möbius inversion: improving on Steiner Tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Proceedings of 36th International Colloquium on Automata, Languages and Programming, ICALP, Part I: Tack A: Algorithms, Automata, Complexity, and Games. Lecture Notes in Computer Science, vol. 5555, pp. 713–725. Springer, Berlin (2009)

    Google Scholar 

  36. Nederlof, J., van Rooij, J.M.M.: Inclusion/exclusion branching for Partial Dominating Set and Set Splitting. In: Raman, V., Saurabh, S. (eds.) Parameterized and Exact Computation—5th International Symposium, IPEC. Lecture Notes in Computer Science, vol. 6478, pp. 204–215. Springer, Berlin (2010)

    Chapter  Google Scholar 

  37. Ozeki, K., Yamashita, T.: Spanning trees: a survey. Graphs Comb. 27, 1–26 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  38. Prieto, E.: Systematic kernelization in FPT algorithm design. Ph.D. Thesis, The University of Newcastle, Australia (2005)

  39. Prieto, E., Sloper, C.: Either/or: Using vertex cover structure in designing FPT-algorithms—the case of k-internal spanning tree. In: Dehne, F.K.H.A., Sack, J.-R., Smid, M.H.M. (eds.) Proceedings of WADS, Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 2748, pp. 465–483. Springer, Berlin (2003)

    Google Scholar 

  40. Prieto, E., Sloper, C.: Reducing to independent set structure—the case of k-internal spanning tree. Nord. J. Comput. 12(3), 308–318 (2005)

    MathSciNet  MATH  Google Scholar 

  41. Raible, D., Fernau, H.: An amortized search tree analysis for k-Leaf Spanning Tree. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorný, J., Rumpe, B. (eds.) SOFSEM: Theory and Practice of Computer Science. Lecture Notes in Computer Science, vol. 5901, pp. 672–684. Springer, Berlin (2010)

    Google Scholar 

  42. Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425–440 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  43. Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Inf. Process. Lett. 105(5), 164–169 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  44. Salamon, G.: Approximation algorithms for the maximum internal spanning tree problem. Theor. Comput. Sci. 410(50), 5273–5284 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  45. Salamon, G.: A survey on algorithms for the maximum internal spanning tree and related problems. Electron. Notes Discrete Math. 36, 1209–1216 (2010)

    Article  Google Scholar 

  46. Sunil Chandran, L., Grandoni, F.: Refined memorization for vertex cover. Inf. Process. Lett. 93, 125–131 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  47. Wahlström, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Linköpings Universitet, Sweden (2007)

Download references

Author information

Authors and Affiliations

  1. FB 4—Abteilung Informatik, Univ. Trier, 54286, Trier, Germany

    Daniel Binkele-Raible & Henning Fernau

  2. Institute of Information Systems (184/3), Vienna Univ. of Technology, Favoritenstraße 9-11, 1040, Wien, Austria

    Serge Gaspers

  3. LIFO, Univ. d’Orléans, 45067, Orléans Cedex 2, France

    Mathieu Liedloff

Authors
  1. Daniel Binkele-Raible
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Henning Fernau
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Serge Gaspers
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mathieu Liedloff
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Henning Fernau.

Additional information

This work was partially supported by a PPP grant between DAAD (Germany) and NFR (Norway). The third author acknowledges partial support from the ERC, grant reference 239962.

A preliminary version of this paper appeared in the proceedings of WG 2009 [14].

Rights and permissions

Reprints and permissions

About this article

Cite this article

Binkele-Raible, D., Fernau, H., Gaspers, S. et al. Exact and Parameterized Algorithms for Max Internal Spanning Tree . Algorithmica 65, 95–128 (2013). https://doi.org/10.1007/s00453-011-9575-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-011-9575-5

Keywords

Search

Navigation