Fixed-Parameter Tractability, Definability, and Model-Checking
From MaRDI portal
Publication:2719133
DOI10.1137/S0097539799360768zbMath0992.68060OpenAlexW1579643516MaRDI QIDQ2719133
Publication date: 21 June 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539799360768
Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Interpolation, preservation, definability (03C40)
Related Items
Simplifying the weft hierarchy, On miniaturized problems in parameterized complexity theory, Describing parameterized complexity classes, Compactors for parameterized counting problems, Characterising bounded expansion by neighbourhood complexity, An analysis of the W*-hierarchy, A Parameterized Halting Problem, Parameterized Complexity Classes under Logical Reductions, Unnamed Item, Parameterized complexity of completeness reasoning for conjunctive queries, On the complexity of various parameterizations of common induced subgraph isomorphism, Fixed-parameter tractable distances to sparse graph classes, Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes, Unnamed Item, Unnamed Item, Parameterized random complexity, Dominating set is fixed parameter tractable in claw-free graphs, First-Order Model-Checking in Random Graphs and Complex Networks, Reducing CMSO model checking to highly connected graphs, The parameterized complexity of maximality and minimality problems, Complexity of Grundy coloring and its variants, Game-based notions of locality over finite models, On the fixed-parameter tractability of parameterized model-checking problems, Machine-based methods in parameterized complexity theory, A parametric analysis of the state-explosion problem in model checking, Unnamed Item, Unnamed Item, On the Parameterised Intractability of Monadic Second-Order Logic, Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree, Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
