The complexity of fixed-parameter problems: guest column

ABSTRACT

We describe how to found and develop the theory of fixed-parameter complexity and hardness in a manner both fully analgous to the classical theory of NP-completeness and much simpler than the original development. We present some recent advance made using this approach.

REFERENCES

• 1: Jonathan F. Buss , Judy Goldsmith, Nondeterminism within P, SIAM Journal on Computing, v.22 n.3, p.560-572, June 1993 [doi>10.1137/0222038]
• 2: Jonathan F. Buss , Tarique Islam, Simplifying the weft hierarchy, Theoretical Computer Science, v.351 n.3, p.303-313, 28 February 2006 [doi>10.1016/j.tcs.2005.10.002]
• 3: Jonathan F. Buss , Tarique Islam, Algorithms in the W-Hierarchy, Theory of Computing Systems, v.41 n.3, p.445-457, October 2007 [doi>10.1007/s00224-007-1325-3]
• 4: J. F. Buss, T. Islam, "The Fixed-Parameter Complexity of Longest-Common-Subsequence and PDA Intersection Problems," in preparation.
• 5: Marco Cesati, The turing way to parameterized complexity, Journal of Computer and System Sciences, v.67 n.4, p.654-685, December 2003 [doi>10.1016/S0022-0000(03)00073-4]
• 6: Y. Chen, J. Flum, "Machine Characterization of the Classes of the W hierarchy," in Computer Science Logic: CSL 2003, Lecture Notes in Computer Science 2803, Springer, 2003, pp. 114--127.
• 7: Y. Chen, J. Flum, M. Grohe, "Bounded Nondeterminism and Alternation in Parameterized Complexity Theory," in 18th Ann. IEEE Conf. Computational Complexity, 2003, pp. 18--29.
• 8: Yijia Chen , Jörg Flum , Martin Grohe, Machine-based methods in parameterized complexity theory, Theoretical Computer Science, v.339 n.2, p.167-199, 12 June 2005 [doi>10.1016/j.tcs.2005.02.003]
• 9: Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
• 10: Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3 ]
• 11: R. G. Downey, M. R. Fellows, Parameterized Complexity, Springer, 1999.
• 12: Jörg Flum , Martin Grohe, Fixed-Parameter Tractability, Definability, and Model-Checking, SIAM Journal on Computing, v.31 n.1, p.113-145, 2001 [doi>10.1137/S0097539799360768]
• 13: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 14: Tarique M. Islam, Characterizing hardness in parameterized complexity, University of Waterloo, Waterloo, Ont., Canada, 2007
• 15: Todd Wareham, The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata, Revised Papers from the 5th International Conference on Implementation and Application of Automata, p.302-310, July 24-25, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  A. General Literature
  A.m MISCELLANEOUS

General Terms:
Theory