zbMATH — the first resource for mathematics

A general method to speed up fixed-parameter-tractable algorithms. (English) Zbl 1014.68064
Summary: A fixed-parameter-tractable algorithm, or FPT algorithm for short, gets an instance \((I,k)\) as its input and has to decide whether \((I,k)\in L\) for some parameterized problem \(L\). Many parameterized algorithms work in two stages: reduction to a problem kernel and bounded search tree. Their time complexity is then of the form \(O(p(|I|)+q(k)\xi^k)\), where \(q(k)\) is the size of the problem kernel. We show how to modify these algorithms to obtain time complexity \(O(p(|I|)+\xi^k)\), if \(q(k)\) is polynomial.

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[1] Balasubramanian, R.; Fellows, M.R.; Raman, V., An improved fixed parameter algorithm for vertex cover, Inform. process. lett., Vol. 65, 3, 163-168, (1998) · Zbl 1337.05095
[2] Cai, L.; Chen, J.; Downey, R.G.; Fellows, M.R., Advice classes of parameterized tractability, Ann. pure appl. logic, Vol. 84, 119-138, (1997) · Zbl 0873.68071
[3] Chen, J.; Kanj, I.; Jia, W., Vertex cover: further observations and further improvements, () · Zbl 0952.68111
[4] Downey, R.G.; Fellows, M.R., Parameterized computational feasibility, (), 219-244 · Zbl 0834.68046
[5] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[6] Downey, R.G.; Fellows, M.R.; Stege, U., Parameterized complexity: A framework for systematically confronting computational intractability, (), 49-100 · Zbl 0935.68046
[7] Fernau, H.; Niedermeier, R., An efficient exact algorithm for constraint bipartite vertex cover, (), 387-397 · Zbl 0945.05055
[8] Greene, D.H.; Knuth, D.E., Mathematics for the analysis of algorithms, 2nd edn., Progress in computer science, (1982), Birkhäuser Boston, MA
[9] Niedermeier, R., Some prospects for efficient fixed parameter algorithms, (), 168-185, (Invited Paper)
[10] Niedermeier, R.; Rossmanith, P., An efficient fixed parameter algorithm for 3-hitting set, (1999), WSI für Informatik, Universität Tübingen Germany, Technical Report WSI-99-18
[11] Niedermeier, R.; Rossmanith, P., Upper bounds for vertex cover further improved, (), 561-570 · Zbl 0921.05046
[12] Stege, U.; Fellows, M., An improved fixed-parameter-tractable algorithm for vertex cover, (1999), Department of Computer Science ETH Zürich, Technical Report 318
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.