Quantified conjunctive queries on partially ordered sets

DOI10.1007/978-3-319-13524-3_11zbMATH Open1456.68096arXiv1408.4263OpenAlexW2245088306MaRDI QIDQ2946013FDOQ2946013

Authors: Simone Bova, Robert Ganian, Stefan Szeider 

Publication date: 15 September 2015

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

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.

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

Recommendations

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Block-Sorted Quantified Conjunctive Queries
• Chain minors are FPT
• On the expressive power of the relational algebra with partially ordered domains
• Optimization of quasiconjunctive queries
• 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)