Quantified conjunctive queries on partially ordered sets

DOI10.1007/978-3-319-13524-3_11MaRDI QIDQ2946013zbMATH OpenOpenAlexFDO

Authors Simone Bova, Robert Ganian, Stefan Szeider

Publication date 15 September 2015

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.4263

zbMATH Keywords

parameterized complexityposetsquantified conjunctive queries

Mathematics Subject Classification ID

Partial orders, general (06A06) Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finite poset (a reflexive, antisymmetric, and transitive directed graph). We prove that the problem is already NP-hard on a certain fixed poset, and investigate structural properties of posets yielding fixed-parameter tractability when the problem is parameterized by the query. Our main algorithmic result is that model checking quantified conjunctive queries on posets of bounded width is fixed-parameter tractable (the width of a poset is the maximum size of a subset of pairwise incomparable elements). We complement our algorithmic result by complexity results with respect to classes of finite posets in a hierarchy of natural poset invariants, establishing its tightness in this sense.

Recommendations

• Quantified conjunctive queries on partially ordered sets
• Faster existential FO model checking on posets
• Faster existential FO model checking on posets

Cites work

• scientific article; zbMATH DE number 6006014 (Why is no real title available?)
• scientific article; zbMATH DE number 978246 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• scientific article; zbMATH DE number 969067 (Why is no real title available?)
• Decomposing quantified conjunctive (or disjunctive) formulas
• Linear time solvable optimization problems on graphs of bounded clique-width
• Methods for algorithmic meta theorems
• Parametrized complexity theory.
• Quantified conjunctive queries on partially ordered sets
• Sparsity. Graphs, structures, and algorithms
• The complexity of constraint satisfaction games and QCSP
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(10)

• Quantified conjunctive queries on partially ordered sets
• Quantified conjunctive queries on partially ordered sets
• Faster existential FO model checking on posets
• Ordering conjunctive queries
• scientific article; zbMATH DE number 7297821 (Why is no real title available?)
• Block-Sorted Quantified Conjunctive Queries
• Chain minors are FPT
• Optimization of quasiconjunctive queries
• On the expressive power of the relational algebra with partially ordered domains
• Faster existential FO model checking on posets

This page was built for publication: Quantified conjunctive queries on partially ordered sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946013)