S. Bova,R. Ganian, St. Szeider:

"Quantified Conjunctive Queries on Partially Ordered Sets";

Talk: International Symposium on Parameterized and Exact Computation (IPEC), Wroclaw, Poland; 2014-09-10 - 2014-09-12; in: "IPEC 2014", LNCS / Springer, 8894 (2014), 122 - 134.

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.

Project Head Stefan Szeider:

Exploiting New Types of Structure for Fixed Parameter Tractability

Project Head Stefan Szeider:

Parameterized Compilation

Project Head Stefan Szeider:

The Parameterized Complexity of Reasoning Problems

Created from the Publication Database of the Vienna University of Technology.