On the complexity of fixed parameter problems

The authors address the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant alpha such that all problems in the family are solvable in time O(n/sup alpha /). The ques...

Full description

Saved in:
Bibliographic Details
Main Authors: Abrahamson, K.R., Fellows, M.R., Ellis, J.A., Mata, M.E.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Contracts
Councils
Feedback
Polynomials
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The authors address the question of why some fixed-parameter problem families solvable in polynomial time seem to be harder than others with respect to fixed-parameter tractability: whether there is a constant alpha such that all problems in the family are solvable in time O(n/sup alpha /). The question is modeled by considering a class of polynomially indexed relations. The main results show that (1) this setting supports notions of completeness that can be used to explain the apparent hardness of certain problems with respect to fixed-parameter tractability, and (2) some natural problems are complete.< >
DOI:10.1109/SFCS.1989.63480