episciences.org_2272_1634926759
1634926759
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
1860-5974
03
07
2005
Volume 1, Issue 1
Model-Checking Problems as a Basis for Parameterized Intractability
Joerg
Flum
Martin
Grohe
Most parameterized complexity classes are defined in terms of a parameterized
version of the Boolean satisfiability problem (the so-called weighted
satisfiability problem). For example, Downey and Fellow's W-hierarchy is of
this form. But there are also classes, for example, the A-hierarchy, that are
more naturally characterised in terms of model-checking problems for certain
fragments of first-order logic.
Downey, Fellows, and Regan were the first to establish a connection between
the two formalisms by giving a characterisation of the W-hierarchy in terms of
first-order model-checking problems. We improve their result and then prove a
similar correspondence between weighted satisfiability and model-checking
problems for the A-hierarchy and the W^*-hierarchy. Thus we obtain very uniform
characterisations of many of the most important parameterized complexity
classes in both formalisms.
Our results can be used to give new, simple proofs of some of the core
results of structural parameterized complexity theory.
03
07
2005
2272
arXiv:cs/0502005
10.2168/LMCS-1(1:2)2005
https://lmcs.episciences.org/2272