Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T16:18:38.092Z Has data issue: false hasContentIssue false
  • English
  • Français

An analysis of the W*-hierarchy

Published online by Cambridge University Press:  12 March 2014

Yijia Chen ,
Jörg Flum  and
Martin Grohe
Yijia Chen
Affiliation:
Basics, Department of Computer Science, Shanghai Jiaotong University, Shanghai 200030, China, E-mail: [email protected]
Jörg Flum
Affiliation:
Abteilung für Mathematische Logik, Universität Freiburg, Eckerstr. 1, 79104 Freiburg, Germany, E-mail: [email protected]
Martin Grohe
Affiliation:
Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We observe that the W*-hierarchy, a variant (introduced by Downey, Fellows, and Taylor [7]) of the better known W-hierarchy, coincides with the W-hierarchy, though not level wise, but just as a whole hierarchy. More precisely, we prove that W[t] ⊆ W* [t] ⊆ W[2t − 2] for each t ≥ 2. It was known before that W[1] = W*[1] and W[2] = W*[2].

Our second main result is a new logical characterization of the W*-hierarchy in terms of “Fagin-definable problems.” As a by-product, we also obtain an improvement of our earlier characterization of the hierarchy in terms of model-checking problems. Furthermore, we obtain new complete problems for the classes W[3] and W*[3].

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 2 , June 2007 , pp. 513 - 534
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Buss, J. F. and Islam, T., Algorithms in the W-hierarchy, Theory of Computing Systems, to appear. Available at http://www.cs.uwaterloo.ca/~jfbuss/.Google Scholar
[2]Downey, R. G. and Fellows, M. R., Fixed-parameter tractability and completeness I: Basic results, SIAM Journal on Computing, vol. 24 (1995), pp. 873–921.CrossRefGoogle Scholar
[3]Downey, R. G. and Fellows, M. R., Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science, vol. 141 (1995), pp. 109–131.CrossRefGoogle Scholar
[4]Downey, R. G. and Fellows, M. R., Threshold dominating sets and an improved characterization of W[2], Theoretical Computer Science, vol. 209 (1998), pp. 123–140.CrossRefGoogle Scholar
[5]Downey, R. G. and Fellows, M. R., Parameterized complexity, Springer-Verlag, 1999.CrossRefGoogle Scholar
[6]Downey, R. G., Fellows, M. R., and Regan, K., Descriptive complexity and the W-hierarchy, Proof complexity andfeasible arithmetic (Beame, P. and Buss, S., editors), AMS-DIMACS Volume Series, vol. 39, AMS, 1998, pp. 119–134.CrossRefGoogle Scholar
[7]Downey, R. G., Fellows, M. R., and Taylor, U., The parameterized complexity of relational database queries and an improved characterization of W[1], Combinatorics, complexity, and logic–proceedings of DMTCS '96 (Bridges, D. S., Calude, C., Gibbons, P., Reeves, S., and Witten, I. H., editors), Springer-Verlag, 1996, pp. 194–213.Google Scholar
[8]Flum, J. and Grohe, M., Fixed-parameter tractability, definability, and model checking, SIAM Journal on Computing, vol. 31 (2001), no. 1, pp. 113–145.CrossRefGoogle Scholar
[9]Flum, J. and Grohe, M., Model-checking problems as a basis for parameterized intractability, Logical Methods in Computer Science, vol. 1 (2005), no. 1.Google Scholar
[10]Flum, J. and Grohe, M., Parameterized complexity theory, Springer-Verlag, 2006.Google Scholar
[11]Landes, J., Die W*-Hierarchie, Diplomarbeit, Universitát Freiburg, 2005.Google Scholar