Helsinki Algorithms Seminar: "Answer Set Programs with Groundings of Small Treewidth" Bernhard Bliem

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design

Bernhard Bliem

Answer Set Programs with Groundings of Small Treewidth

Abstract:

State-of-the-art Answer Set Programming (ASP) solvers are based on algorithms that do not explicitly consider treewidth. Yet the treewidth of the input seems to have a strong influence their performance. In the first part of this talk, we present experiments that confirm that suspicion. In the second part, we ask how we can turn this observation to our advantage in practice. This is not obvious because the input for the ASP solver may have much higher treewidth than the actual problem instance. The reason is that ASP is typically used in such a way that the problem at hand is encoded as a (non-ground, i.e., first-order) ASP specification, which, in an intermediate step, is transformed together with the problem instance into a ground (i.e., propositional) ASP program that can then be given to the solver. The treewidth that the solver encounters therefore depends not only on the treewidth of the instance, but it may be much higher if we choose our ASP encoding unwisely. We prove that a class of non-ground programs called guarded ASP guarantees that the grounding process does not significantly increase the treewidth. We also present a related class called connection-guarded ASP, which admits groundings whose treewidth depends on both the treewidth and the maximum degree of the input, and we show  that this dependency on the maximum degree cannot be dropped.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

Welcome!