Advice classes of parameterized tractability Academic Article uri icon

abstract

  • 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 parameterized 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 parameterized analog of P) has interesting and natural internal structure.

published proceedings

  • Annals of Pure and Applied Logic

author list (cited authors)

  • Cai, L., Chen, J., Downey, R. G., & Fellows, M. R.

citation count

  • 84

complete list of authors

  • Cai, Liming||Chen, Jianer||Downey, Rodney G||Fellows, Michael R

publication date

  • March 1997