DSpace-CRIS at TU Wienhttps://repositum.tuwien.atThe reposiTUm digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sat, 10 Dec 2022 03:20:51 GMT2022-12-10T03:20:51Z5021Model Checking Existential Logic on Partially Ordered Setshttp://hdl.handle.net/20.500.12708/55811Title: Model Checking Existential Logic on Partially Ordered Sets
Authors: Bova, Simone; Ganian, Robert; Szeider, Stefan
Abstract: We study the problem of checking whether an existential sentence
(that is, a first-order sentence in prefix form built using existential
quantifiers and all Boolean connectives) is true in a finite partially
ordered set (in short, a poset). A poset is a reflexive, antisymmetric,
and transitive digraph. The problem encompasses the fundamental
embedding problem of finding an isomorphic copy of a poset as an
induced substructure of another poset.
Model checking existential logic is already NP-hard on a fixed
poset; thus we investigate structural properties of posets yielding
conditions for fixed-parameter tractability when the problem is
parameterized by the sentence. We identify width as a central
structural property (the width of a poset is the maximum size of a
subset of pairwise incomparable elements); our main algorithmic
result is that model checking existential logic on classes of finite
posets of bounded width is fixed-parameter tractable. We observe a
similar phenomenon in classical complexity, where we prove that
the isomorphism problem is polynomial-time tractable on classes
of posets of bounded width; this settles an open problem in order
theory.
We surround our main algorithmic result with complexity results
on less restricted, natural neighboring classes of finite posets,
establishing its tightness in this sense. We also relate our work
with (and demonstrate its independence of) fundamental fixedparameter
tractability results for model checking on digraphs of
bounded degree and bounded clique-width.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/20.500.12708/558112014-01-01T00:00:00ZQuantified Conjunctive Queries on Partially Ordered Setshttp://hdl.handle.net/20.500.12708/55812Title: Quantified Conjunctive Queries on Partially Ordered Sets
Authors: Bova, Simone; Ganian, Robert; Szeider, Stefan
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.
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/20.500.12708/558122014-01-01T00:00:00Z