Abstract
We describe some new, simple and apparently general methods for designing FPT algorithms, and illustrate how these can be used to obtain a significantly improved FPT algorithm for the Maximum Leaf Spanning Tree problem. Furthermore, we sketch how the methods can be applied to a number of other well-known problems, including the parametric dual of Dominating Set (also known as Nonblocker), Matrix Domination, Edge Dominating Set, and Feedback Vertex Set for Undirected Graphs. The main payoffs of these new methods are in improved functions f(k) in the FPT running times, and in general systematic approaches that seem to apply to a wide variety of problems.
Ulrike Stege is supported by the Pacific Institute for the Mathematical Sciences (PIMS), where she is a postdoctoral fellow.
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
H. L. Bodlaender. “On linear time minor tests and depth-first search.” In F. Dehne et al. (eds.), Proc. First Workshop on Algorithms and Data Structures, LNCS 382, pp. 577–590, 1989.
R. Balasubramanian, M. R. Fellows, and V. Raman. “An Improved Fixed-Parameter Algorithm for Vertex Cover.” Information Processing Letters 65:3, pp. 163–168, 1998.
B. Berger, T. Leighton. “Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete.” In S. Istrail, P. Pevzner, and M. Waterman (eds.), Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB98), pp. 30–39, 1998.
[CCDF97] L. Cai, J. Chen, R. Downey, and M. Fellows. “The parameterized complexity of short computation and factorization.” Archive for Mathematical Logic 36, pp. 321–338, 1997.
P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni and M. Yan-nakakis. “On the complexity of protein folding.” In S. Istrail, P. Pevzner, and M. Waterman (eds.), Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB98), 1998.
J. Chen, I. Kanj, and W. Jia. “Vertex cover: Further Observations and Further Improvements.” 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’99) Ascona, Switzerland, June 1999.
R. Downey and M. Fellows. “Parameterized Computational Feasibility.” P. Clote, J. Remmel (eds.): Feasible Mathematics II Boston: Birkhauser, pp. 219–244, 1995.
R. Downey and M. Fellows. “Fixed-parameter tractability and completeness II: completeness for W[1].” Theoretical Computer Science A 141, pp. 109–131, 1995.
R. Downey and M. Fellows. Parameterized Complexity. Springer-Verlag, 1998.
R. Downey, M. Fellows, and U. Stege. “Parameterized complexity: a framework for systematically confronting computational intractability.” In: Contemporary Trends in Discrete Mathematics (R. Graham, J. Kratochvil, J. Nesetril and F. Roberts, eds.), AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 49, pp. 49–99, 1999.
E. Dijkstra. “Self-Stabilizing Systems in Spite of Distributed Control.” Communications of the ACM 17, pp. 643–644, 1974.
M. Fellows and M. Langston. “On Well-Partial-Order Theory and Its Applications to Combinatorial Problems of VLSI Design.” Technical Report CS-88-188, Department of Computer Science, Washington State University, 1988.
M. Fellows, C. McCartin, F. Rosamond, and U. Stege. “The parametric dual of Dominating Set is fixed-parameter tractable,” 2000.
G. Galbiati, F. Maffioli, and A. Morzenti. “A Short Note on the Approxima-bility of the Maximum Leaves Spanning Tree Problem.” Information Processing Letters 52, pp. 45–49, 1994.
G. Galbiati, A. Morzenti and F. Maffioli. “On the Approximability of some Maximum Spanning Tree Problems.” Theoretical Computer Science 181, pp. 107–118, 1997.
M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, 1979.
T. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc, 1998.
E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia, G. Woeginger. “VC-dimensions for graphs.” In M. Nagl, editor, Graph-theoretic concepts in computer science, LNCS 1017, pp. 1–13, 1995.
H.-I. Lu and R. Ravi. “Approximating Maximum Leaf Spanning Trees in Almost Linear Time.” Journal of Algorithms 29, pp. 132–141, 1998.
R. Niedermeier and P. Rossmanith. “Upper Bounds for Vertex Cover Further Improved.” In C. Meinel and S. Tison, editors, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, LNCS 1563, pp. 561–570, 1999.
R. Niedermeier and P. Rossmanith. “A General Method to Speed Up Fixed-Parameter-Tractable Algorithms.” Information Processing Letters, 73, pp. 125–129, 2000.
R. Niedermeier and P. Rossmanith. “An efficient fixed parameter algorithm for 3-Hitting Set.” accepted for publication in Journal of Discrete Algorithms, August 2000.
U. Stege. Resolving Conflicts from Computational Biology. Ph.D. thesis, Department of Computer Science, ETH Zürich, Switzerland, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Michael, R.F., McCartin, C., Frances, A.R., Stege, U. (2000). Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems. In: Kapoor, S., Prasad, S. (eds) FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2000. Lecture Notes in Computer Science, vol 1974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44450-5_19
Download citation
DOI: https://doi.org/10.1007/3-540-44450-5_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41413-1
Online ISBN: 978-3-540-44450-3
eBook Packages: Springer Book Archive