Revision as of 10:05, 20 January 2010 edit Ylloh (talk \| contribs) Extended confirmed users 913 edits m →References: improved references ← Previous edit		Revision as of 10:05, 20 January 2010 edit undo Ylloh (talk \| contribs) Extended confirmed users 913 edits →W[1]: removed another big-O Next edit →
Line 40: '''W[1]''' includes the first class of problems not believed to be in FPT. An example is deciding if an ''n''-vertex graph contains an [[independent set]] of cardinality ''k''. This question can be decided in time <math>O(n^kn^2)</math> by inspecting all vertex subsets of size ''k''; this running time is not fixed-parameter tractable, and no algorithm with a running time of the form <math>O(f(k)n^{O(1)})</math> is known. ===W[2]===

Parameterized complexity: Difference between revisions