×

zbMATH — the first resource for mathematics

Advice classes of parametrized tractability. (English) Zbl 0873.68071
Ann. Pure Appl. Logic 84, No. 1, 119-138 (1997); corrigendum ibid. 169, No. 5, 463-465 (2018).
Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parametrized problems that can be solved (uniformly with respect to the parameter) in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it is shown that the class FPT of tractable parameterized problems (the parametrized analog of P) has interesting and natural internal structure.

MSC:
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrahamson, K.; Downey, R.; Fellows, M., Fixed-parameter intractability II, (), 374-385 · Zbl 0799.68086
[2] Abrahamson, K.; Downey, R.; Fellows, M., Fixed-parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues, Ann. pure appl. logic, 73, 235-276, (1995) · Zbl 0828.68077
[3] Abrahamson, K.; Fellows, M., Finite automata, bounded treewidth, and well-quasiordering, (), 539-564 · Zbl 0791.05094
[4] Bienstock, D.; Monma, C.L., On the complexity of covering vertices by faces in a planar graph, SIAM J. comp., 17, 53-76, (1988) · Zbl 0646.68085
[5] Bodlaender, H.L., Linear time minor tests and depth first search, (), 577-590 · Zbl 0766.68102
[6] Bodlaender, H.L., On disjoint cycles, () · Zbl 0815.05040
[7] Bodlaender, H.L.; Fellows, M.R.; Warnow, T., Two strikes against perfect phylogeny, (), 273-283
[8] Buss, J.F.; Goldsmith, J., Nondeterminism within P, SIAM J. comp., 22, 560-572, (1993) · Zbl 0773.68031
[9] Cai, L.; Chen, J.; Cai, L.; Chen, J., Mfcs’93, (), 311-320, to appear
[10] L. Cai, J. Chen, R. Downey and M. Fellows, The complexity of short computation and factorization, Archive for Mathematical Logic, to appear. · Zbl 0944.68069
[11] Courcelle, B., Graph rewriting: an algebraic and logical approach, (), Chap. 5 · Zbl 0644.68096
[12] Downey, R.G.; Fellows, M.R., Fixed parameter tractability and completeness, (), 161-187 · Zbl 0768.68136
[13] Downey, R.G.; Fellows, M.R., Fixed parameter intractability (extended abstract), (), 36-50
[14] Downey, R.G.; Fellows, M.R., Fixed parameter tractability and completeness III: some structural aspects of the W-hierarchy, (), 166-191 · Zbl 0799.68087
[15] Downey, R.G.; Fellows, M.F., Parameterized computational feasibility, (), 219-244 · Zbl 0834.68046
[16] Downey, R.G.; Fellows, M.R., Fixed parameter tractability and completeness I: basic results, SIAM J. comput., 24, 873-921, (1995) · Zbl 0830.68063
[17] Downey, R.G.; Fellows, M.R., Fixed parameter tractability and completeness II: on completeness for W[1], Theoretical comput. sci., 141, 109-131, (1995) · Zbl 0873.68059
[18] R.G. Downey and M.R. Fellows, Parameterized complexity, monograph in preparation. · Zbl 0914.68076
[19] Fellows, M.R.; Hallett, M.T.; Wareham, H.T., DNA physical mapping: three ways difficult, (), 157-168
[20] Fellows, M.R.; Koblitz, N., Fixed-parameter complexity and cryptography, () · Zbl 0801.68088
[21] Fellows, M.R.; Langston, M.A., On search, decision and the efficiency of polynomial-time algorithms, (), 501-512
[22] Fellows, M.R.; Langston, M.A., An analogue of the myhill-nerode theorem and its use in computing finite basis characterizations, (), 520-525
[23] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[24] Johnson, D.S., A catalogue of complexity classes, (), 68-161
[25] Lipton, R.; Zalcstein, Y., Word problems solvable in logspace, J. assoc. comput. Mach., 24, 522-526, (1977) · Zbl 0359.68049
[26] Nesetril, J.; Poljak, S., On the complexity of the subgraph problem, Comm. math. univ. carol., 26, 415-419, (1985) · Zbl 0571.05050
[27] Regan, K., Finitary substructure languages, with application to the theory of NP-completeness, (), 87-96
[28] N. Robertson and P.D. Seymour, Graph minors XIII. The disjoint paths problem, J. Comb. Theory B. to appear. · Zbl 0823.05038
[29] N. Robertson and P.D. Seymour, Graph minors XV. Wagner’s Conjecture, J. Comp. Theory B. to appear. · Zbl 1061.05088
[30] van Leeuwen, J., ()
[31] van Leeuwen, J., Graph algorithms, (), 527-632
[32] Papadimitriou, C.; Yannakakis, M., On limited nonterminism and the complexity of the V-C dimension, (), 12-18
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.