Fixed-parameter tractability, definability, and model checking
| dc.creator | Flum, Joerg | |
| dc.creator | Grohe, Martin | |
| dc.date | 1999-10-01 | |
| dc.date | 2001-02-19 | |
| dc.date.accessioned | 2026-07-07T03:24:22Z | |
| dc.date.available | 2026-07-07T03:24:22Z | |
| dc.description | In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every t >= 0 we prove an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows' W-hierarchy. On a more abstract level, we consider two forms of definability, called Fagin definability and slicewise definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic, which is reminiscent of the Immerman-Vardi Theorem characterizing the class PTIME in terms of definability in least fixed-point logic. | |
| dc.description | To appear in SIAM Journal on Computing | |
| dc.identifier | https://arxiv.org/abs/cs/9910001 | |
| dc.identifier | http://arxiv.org/abs/cs/9910001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33300 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.1.3;F.4.1 | |
| dc.title | Fixed-parameter tractability, definability, and model checking | |
| dc.type | text |