×

zbMATH — the first resource for mathematics

Fixed-parameter tractability and completeness II: On completeness for W[1]. (English) Zbl 0873.68059
Summary: For many fixed-parameter problems that are trivially solvable in polynomial-time, such as \(k\)-DOMINATING SET, essentially no better algorithm is presently known than the one which tries all possible solutions. Other problems, such as FEEDBACK VERTEX SET, exhibit fixed-parameter tractability: for each fixed \(k\) the problem is solvable in time bounded by a polynomial of degree \(c\), where \(c\) is a constant independent of \(k\). In a previous paper, the W Hierarchy of parameterized problems was defined, and complete problems were identified for the classes W[\(t\)] for \(t\geq 2\). Our main result shows that INDEPENDENT SET is complete for W[1].

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Keywords:
independent set
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrahamson, K.A.; Downey, R.G.; Fellows, M.F., Fixed-parameter intractability II, (), 374-385 · Zbl 0799.68086
[2] K.A. Abrahamson, R.G. Downey and M.R. Fellows, Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE Analogues, Ann. Pure Appl. Logic, to appear. · Zbl 0828.68077
[3] Buss, J.F.; Goldsmith, J., Nondeterminism, within P, SIAM J. comput., 22, 560-572, (1993) · Zbl 0773.68031
[4] Bodlaender, H.L., On disjoint cycles, () · Zbl 0815.05040
[5] Bodlaender, H.L.; Downey, R.G.; Fellows, M.R.; Wareham, H.Todd, The parameterized complexity of sequence alignment and concensus (extended abstract), (), 15-30, Final version to appear in Theoret. Comput. Sci.
[6] L. Cai, J. Chen, R.G. Downey and M.F. Fellows, The parameterized complexity of short computation and factorization, submitted. · Zbl 0944.68069
[7] Downey, R.G.; Evans, P.; Fellows, M.F., Parameterized learning complexity, (), 51-57
[8] Downey, R.G.; Fellows, M.R., Fixed-parameter tractability and completeness, (), 161-187 · Zbl 0768.68136
[9] Downey, R.G.; Fellows, M.F., Fixed-parameter intractability, (), 36-49
[10] Downey, R.G.; Fellows, M.R., Fixed-parameter tractability and completeness III: some structural aspects of the W-hierarchy, (), 166-191 · Zbl 0799.68087
[11] R.G. Downey and M.R. Fellows, Fixed-parameter tractability and completeness I: Basic results, SIAM J. Comput., to appear. · Zbl 0830.68063
[12] R.G. Downey and M.F. Fellows, Parameterized computational feasibility, in: P. Clote and J. Remmel, eds., Feasible Mathematics II (Birkhauser, Boston) to appear. · Zbl 0834.68046
[13] R.G. Downey and M.F. Fellows, Parameterized Complexity, monograph, in preparation. · Zbl 0914.68076
[14] R.G. Downey and M.F. Fellows, Fixed-parameter tractability and intractability — A survey, in preparation. · Zbl 0799.68087
[15] Fellows, M.R.; Langston, M.A., On search, decision and the efficiency of polynomial-time algorithms, (), 501-512
[16] Fellows, M.R.; Langston, M.A., An analogue of the myhill-nerode theorem and its use in computing finite basis characterizations, (), 520-525
[17] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[18] Papadimitriou, C.; Yannakakis, M., On limited nondeterminism and the complexity of the VC-dimension, (), 12-18
[19] N. Robertson and P.D. Seymour, Graph minors XIII. The disjoint paths problem, to appear. · Zbl 0823.05038
[20] N. Robertson and P.D. Seymour, Graph minors XV. Wagner’s conjecture, to appear. · Zbl 1061.05088
[21] van Leeuwen, J., Graph algorithms, (), 525-632 · Zbl 0900.68258
[22] Downey, R.G.; Fellows, M.; Kapron, B.; Hallet, M.; Wareham, H.Todd, The parameterized complexity of some problems in logic and linguistics (extended abstract), (), 89-101 · Zbl 0946.03046
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.