Abstract
To determine if a graph has a spanning tree with few leaves is NP-hard. In this paper we study the parametric dual of this problem, k-Internal Spanning Tree (Does G have a spanning tree with at least k internal vertices?). We give an algorithm running in time O(24klogk ·k 7/2 + k 2 ·n 2). We also give a 2-approximation algorithm for the problem.
However, the main contribution of this paper is that we show the following remarkable structural bindings between k-Internal Spanning Tree and k-Vertex Cover:
-
No for k-Vertex Cover implies Yes for k-Internal Spanning Tree.
-
Yes for k-Vertex Cover implies No for (2k+1)-Internal Spanning Tree.
We give a polynomial-time algorithm that produces either a vertex cover of size kor a spanning tree with at least k internal vertices. We show how to use this inherent vertex cover structure to design algorithms for FPT problems, here illustrated mainly by k-Internal Spanning Tree. We also briefly discuss the application of this vertex cover methodology to the parametric dual of the Dominating Set problem. This design technique seems to apply to many other FPT problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.: Private communication
Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 613–627. Springer, Heidelberg (2002)
Balasubramanian, R., Fellows, M.R., Raman, V.: An Improved Fixed Parameter Algorithm for Vertex Cover. Information Processing Letters 65(3), 163–168 (1998)
Chor, B., Fellows, M., Juedes, D.: Private communication concerning (manuscript) (in preparation)
Cai, L., Chen, J., Downey, R., Fellows, M.: The parameterized complexity of short computation and factorization. Archive for Mathematical Logic 36, 321–338 (1997)
Chen, J., Kanj, I., Jia, W.: Vertex cover: Further Observations and Further Improvements. Journal of Algorithms 41, 280–301 (2001)
Cormen, T.H., Leierson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge
Downey, R., Fellows, M.: Parameterized Computational Feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219–244. Birkhauser, Boston (1995)
Downey, R., Fellows, M.: Fixed-parameter tractability and completeness II: completeness for W[1]. Theoretical Computer Science A 141, 109–131 (1995)
Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1998)
Downey, R., Fellows, M., Stege, U.: Parameterized complexity: a framework for systematically confronting computational intractability. In: Graham, R., Kratochvil, J., Nesetril, J., Roberts, F. (eds.) Contemporary Trends in Discrete Mathematics. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, pp. 49–99 (1999)
Faisal, A., Fellows, M., Langston, M., Rosamond, F.: Private communication concerning (manuscript) (in preparation)
Fellows, M., McCartin, C., Rosamond, F., Stege, U.: Spanning Trees with Few and Many Leaves (to appear)
Galbiati, G., Maffioli, F., Morzenti, A.: A Short Note on the Approximability of the Maximum Leaves Spanning Tree Problem. Information Processing Letters 52, 45–49 (1994)
Galbiati, G., Morzenti, A., Maffioli, F.: On the Approximability of some Maximum Spanning Tree Problems. Theoretical Computer Science 181, 107–118 (1997)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)
Khot, S., Raman, V.: Parameterized Complexity of Finding Hereditary Properties. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol. 1858, p. 137. Springer, Heidelberg (2000); Theoretical Computer Science (COCOON 2000 special issue)
Langston, M.: Private communication
Lu, H.-I., Ravi, R.: Approximating Maximum Leaf Spanning Trees in Almost Linear Time. Journal of Algorithms 29, 132–141 (1998)
McCartin, C.: Ph.D. dissertation in Computer Science, Victoria University, Wellington, New Zealand (2003)
Niedermeier, R., Rossmanith, P.: Upper Bounds for Vertex Cover Further Improved. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 561–570. Springer, Heidelberg (1999)
Telle, J.A., Proskurowski, A.: Practical algorithms on partial k-trees with an application to domination-like problems. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol. 709, pp. 610–621. Springer, Heidelberg (1993)
Robertson, N., Seymor, P.D.: Graph Minors. XX Wagner’s conjecture (to appear)
Stege, U.: Ph.D. dissertation in Computer Science, ETH, Zurich, Switzerland (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Prieto, E., Sloper, C. (2003). Either/Or: Using Vertex Cover Structure in Designing FPT-Algorithms — the Case of k-Internal Spanning Tree . In: Dehne, F., Sack, JR., Smid, M. (eds) Algorithms and Data Structures. WADS 2003. Lecture Notes in Computer Science, vol 2748. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45078-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-45078-8_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40545-0
Online ISBN: 978-3-540-45078-8
eBook Packages: Springer Book Archive