Arrow Research search

Author name cluster

Bernhard Bliem

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

JAIR Journal 2020 Journal Article

The Impact of Treewidth on Grounding and Solving of Answer Set Programs

  • Bernhard Bliem
  • Michael Morak
  • Marius Moldovan
  • Stefan Woltran

In this paper, we aim to study how the performance of modern answer set programming (ASP) solvers is influenced by the treewidth of the input program and to investigate the consequences of this relationship. We first perform an experimental evaluation that shows that the solving performance is heavily influenced by treewidth, given ground input programs that are otherwise uniform, both in size and construction. This observation leads to an important question for ASP, namely, how to design encodings such that the treewidth of the resulting ground program remains small. To this end, we study two classes of disjunctive programs, namely guarded and connection-guarded programs. In order to investigate these classes, we formalize the grounding process using MSO transductions. Our main results show that both classes guarantee that the treewidth of the program after grounding only depends on the treewidth (and the maximum degree, in case of connection-guarded programs) of the input instance. In terms of parameterized complexity, our findings yield corresponding FPT results for answer-set existence for bounded treewidth (and also degree, for connection-guarded programs) of the input instance. We further show that bounding treewidth alone leads to NP-hardness in the data complexity for connection-guarded programs, which indicates that the two classes are fundamentally different. Finally, we show that for both classes, the data complexity remains as hard as in the general case of ASP.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

The Impact of Treewidth on ASP Grounding and Solving

  • Bernhard Bliem
  • Marius Moldovan
  • Michael Morak
  • Stefan Woltran

In this paper, we aim to study how the performance of modern answer set programming (ASP) solvers is influenced by the treewidth of the input program and to investigate the consequences of this relationship. We first perform an experimental evaluation that shows that the solving performance is heavily influenced by the treewidth, given ground input programs that are otherwise uniform, both in size and construction. This observation leads to an important question for ASP, namely, how to design encodings such that the treewidth of the resulting ground program remains small. To this end, we define the class of connection-guarded programs, which guarantees that the treewidth of the program after grounding only depends on the treewidth (and the degree) of the input instance. In order to obtain this result, we formalize the grounding process using MSO transductions.

PDF Details

IJCAI Conference 2016 Conference Paper

ASP for Anytime Dynamic Programming on Tree Decompositions

  • Bernhard Bliem
  • Benjamin Kaufmann
  • Torsten Schaub
  • Stefan Woltran

Answer Set Programming (ASP) has recently been employed to specify and run dynamic programming (DP) algorithms on tree decompositions, a central approach in the field of parameterized complexity, which aims at solving hard problems efficiently for instances of certain structure. This ASP-based method followed the standard DP approach where tables are computed in a bottom-up fashion, yielding good results for several counting or enumeration problems. However, for optimization problems this approach lacks the possibility to report solutions before the optimum is found, and for search problems it often computes a lot of unnecessary rows. In this paper, we present a novel ASP-based system allowing for "lazy" DP, which utilizes recent multi-shot ASP technology. Preliminary experimental results show that this approach not only yields better performance for search problems, but also outperforms some state-of-the-art ASP encodings for optimization problems in terms of anytime computation, i. e. , measuring the quality of the best solution after a certain timeout.

PDF Details

ECAI Conference 2016 Conference Paper

Clique-Width and Directed Width Measures for Answer-Set Programming

  • Bernhard Bliem
  • Sebastian Ordyniak
  • Stefan Woltran

Disjunctive Answer Set Programming (ASP) is a powerful declarative programming paradigm whose main decision problems are located on the second level of the polynomial hierarchy. Identifying tractable fragments and developing efficient algorithms for such fragments are thus important objectives in order to complement the sophisticated ASP systems available to date. Hard problems can become tractable if some problem parameter is bounded by a fixed constant; such problems are then called fixed-parameter tractable (FPT). While several FPT results for ASP exist, parameters that relate to directed or signed graphs representing the program at hand have been neglected so far. In this paper, we first give some negative observations showing that directed width measures on the dependency graph of a program do not lead to FPT results. We then consider the graph parameter of signed clique-width and present a novel dynamic programming algorithm that is FPT w. r. t. this parameter. Clique-width is more general than the well-known treewidth, and, to the best of our knowledge, ours is the first FPT algorithm for bounded clique-width for reasoning problems beyond SAT.

Details

IJCAI Conference 2016 Conference Paper

Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

  • Bernhard Bliem
  • Robert Bredereck
  • Rolf Niedermeier

We study the problem of finding a Pareto-efficient and envy-free allocation of a set of indivisible resources to a set of agents with monotonic preferences, either dichotomous or additive. Motivated by results of Bouveret and Lang [JAIR 2008], we provide a refined computational complexity analysis by studying the influence of three natural parameters: the number n of agents, the number m of resources, and the number z of different numbers occurring in utility-based preferences of the agents. On the negative side, we show that small values for n and z alone do not significantly lower the computational complexity in most cases. On the positive side, devising fixed-parameter algorithms we show that all considered problems are tractable in case of small m. Furthermore, we develop a fixed-parameter algorithm indicating that the problem with additive preferences becomes computationally tractable in case of small n and small z.

PDF Details

JELIA Conference 2014 Conference Paper

The D-FLAT System for Dynamic Programming on Tree Decompositions

  • Michael Abseher
  • Bernhard Bliem
  • Günther Charwat
  • Frederico Dusberger
  • Markus Hecher
  • Stefan Woltran

Abstract Complex reasoning problems over large amounts of data pose a great challenge for computer science. To overcome the obstacle of high computational complexity, exploiting structure by means of tree decompositions has proved to be effective in many cases. However, the implementation of suitable efficient algorithms is often tedious. D-FLAT is a software system that combines the logic programming language Answer Set Programming with problem solving on tree decompositions and can serve as a rapid prototyping tool for such algorithms. Since we initially proposed D-FLAT, we have made major changes to the system, improving its range of applicability and its usability. In this paper, we present the system resulting from these efforts.

Details
v2026.09.13