Arrow Research search

Author name cluster

Andreas Pfandler

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.

16 papers
2 author rows

Possible papers

16

AAAI Conference 2020 Conference Paper

Proportional Belief Merging

  • Adrian Haret
  • Martin Lackner
  • Andreas Pfandler
  • Johannes P. Wallner

In this paper we introduce proportionality to belief merging. Belief merging is a framework for aggregating information presented in the form of propositional formulas, and it generalizes many aggregation models in social choice. In our analysis, two incompatible notions of proportionality emerge: one similar to standard notions of proportionality in social choice, the other more in tune with the logic-based merging setting. Since established merging operators meet neither of these proportionality requirements, we design new proportional belief merging operators. We analyze the proposed operators against established rationality postulates, finding that current approaches to proportionality from the field of social choice are, at their core, incompatible with standard rationality postulates in belief merging. We provide characterization results that explain the underlying conflict, and provide a complexity analysis of our novel operators.

PDF Details

AIJ Journal 2019 Journal Article

Backdoors to planning

  • Martin Kronegger
  • Sebastian Ordyniak
  • Andreas Pfandler

Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms for hard problems in AI and beyond. Despite their success, backdoors have not been used for planning, a central problem in AI that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. For several interesting cases we achieve the most desirable outcome: detection and evaluation are fpt. In addition, we explore the power of polynomial preprocessing for all fpt-results, i. e. , we investigate whether polynomial kernels exist. We show that for the detection problems, polynomial kernels exist whereas we rule out the existence of polynomial kernels for the evaluation problems.

Details DOI

JAIR Journal 2017 Journal Article

Computational Aspects of Nearly Single-Peaked Electorates

  • Gábor Erdélyi
  • Martin Lackner
  • Andreas Pfandler

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.

PDF Details DOI

ECAI Conference 2016 Conference Paper

Beyond IC Postulates: Classification Criteria for Merging Operators

  • Adrian Haret
  • Andreas Pfandler
  • Stefan Woltran

Merging is one of the central operations in the field of belief change, which is concerned with aggregating the opinions of individuals. Representation theorems provide a family of merging operators satisfying some natural desiderata for merging beliefs. However, little is known about how these operators can be further distinguished. In the field of social choice, on the other hand, numerous properties have been proposed in order to classify voting rules. In this work, we adapt these properties to the context of merging and investigate how they relate to the standard postulates. Our results thus lead to a more fine-grained classification of merging operators and shed light on the question of which particular merging operator is best suited in a concrete application domain.

Details

IJCAI Conference 2015 Conference Paper

Distance-Bounded Consistent Query Answering

  • Andreas Pfandler
  • Emanuel Sallinger

The ability to perform reasoning on inconsistent data is a central problem both for AI and database research. One approach to deal with this situation is consistent query answering, where queries are answered over all possible repairs of the database. In general, the repair may be very distant from the original database. In this work we present a new approach where this distance is bounded and analyze its computational complexity. Our results show that in many (but not all) cases the complexity drops.

PDF Details

IJCAI Conference 2015 Conference Paper

Fixed-Parameter Tractable Reductions to SAT for Planning

  • Ronald de Haan
  • Martin Kronegger
  • Andreas Pfandler

Planning is an important AI task that gives rise to many hard problems. In order to come up with efficient algorithms for this setting, it is important to understand the sources of complexity. For planning problems that are beyond NP, identifying fragments that allow an efficient reduction to SAT can be a feasible approach due to the great performance of modern SAT solvers. In this paper, we use the framework of parameterized complexity theory to obtain a more fine-grained complexity analysis of natural planning problems beyond NP. With this analysis we are able to point out several variants of planning where the structure in the input makes encodings into SAT feasible. We complement these positive results with some hardness results and a new machine characterization for the intractability class ∃∗ ∀k -W[P].

PDF Details

IJCAI Conference 2015 Conference Paper

On the Parameterized Complexity of Belief Revision

  • Andreas Pfandler
  • Stefan R
  • uuml; mmele
  • Johannes Peter Wallner
  • Stefan Woltran

Parameterized complexity is a well recognized vehicle for understanding the multitude of complexity AI problems typically exhibit. However, the prominent problem of belief revision has not undergone a systematic investigation in this direction yet. This is somewhat surprising, since by its very nature of involving a knowledge base and a revision formula, this problem provides a perfect playground for investigating novel parameters. Among our results on the parameterized complexity of revision is thus a versatile fpt algorithm which is based on the parameter of the number of atoms shared by the knowledge base and the revision formula. Towards identifying the frontier between parameterized tractability and intractability, we also give hardness results for classes such as co-W[1], para-ΘP 2, and FPTNP [f(k)].

PDF Details

AAAI Conference 2015 Conference Paper

Variable-Deletion Backdoors to Planning

  • Martin Kronegger
  • Sebastian Ordyniak
  • Andreas Pfandler

Backdoors are a powerful tool to obtain efficient algorithms for hard problems. Recently, two new notions of backdoors to planning were introduced. However, for one of the new notions (i. e. , variable-deletion) only hardness results are known so far. In this work we improve the situation by defining a new type of variabledeletion backdoors based on the extended causal graph of a planning instance. For this notion of backdoors several fixed-parameter tractable algorithms are identified. Furthermore, we explore the capabilities of polynomial time preprocessing, i. e. , we check whether there exists a polynomial kernel. Our results also show the close connection between planning and verification problems such as Vector Addition System with States (VASS).

PDF Details

AAAI Conference 2014 Conference Paper

A Parameterized Complexity Analysis of Generalized CP-Nets

  • Martin Kronegger
  • Martin Lackner
  • Andreas Pfandler
  • Reinhard Pichler

Generalized CP-nets (GCP-nets) allow a succinct representation of preferences over multi-attribute domains. As a consequence of their succinct representation, many GCP-net related tasks are computationally hard. Even finding the more preferable of two outcomes is PSPACE-complete. In this work, we employ the framework of parameterized complexity to achieve two goals: First, we want to gain a deeper understanding of the complexity of GCP-nets. Second, we search for efficient fixed-parameter tractable algorithms.

PDF Details

AAAI Conference 2014 Conference Paper

Backdoors to Planning

  • Martin Kronegger
  • Sebastian Ordyniak
  • Andreas Pfandler

Backdoors measure the distance to tractable fragments and have become an important tool to find fixed-parameter tractable (fpt) algorithms. Despite their success, backdoors have not been used for planning, a central problem in AI that has a high computational complexity. In this work, we introduce two notions of backdoors building upon the causal graph. We analyze the complexity of finding a small backdoor (detection) and using the backdoor to solve the problem (evaluation) in the light of planning with (un)bounded plan length/domain of the variables. For each setting we present either an fpt-result or rule out the existence thereof by showing parameterized intractability. In three cases we achieve the most desirable outcome: detection and evaluation are fpt.

PDF Details

IJCAI Conference 2013 Conference Paper

Backdoors to Abduction

  • Andreas Pfandler
  • Stefan Rümmele
  • Stefan Szeider

Abductive reasoning (or Abduction, for short) is among the most fundamental AI reasoning methods, with a broad range of applications, including fault diagnosis, belief revision, and automated planning. Unfortunately, Abduction is of high computational complexity; even propositional Abduction is ΣP 2-complete and thus harder than NP and co-NP. This complexity barrier rules out the existence of a polynomial transformation to propositional satisfiability (SAT). In this work we use structural properties of the Abduction instance to break this complexity barrier. We utilize the problem structure in terms of small backdoor sets. We present fixedparameter tractable transformations from Abduction to SAT, which make the power of today’s SAT solvers available to Abduction.

PDF Details DOI

AAAI Conference 2013 Conference Paper

Computational Aspects of Nearly Single-Peaked Electorates

  • Gábor Erdélyi
  • Martin Lackner
  • Andreas Pfandler

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra (2011b) studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. Furthermore, we explore the relations between several notions of nearly singlepeakedness.

PDF Details

IJCAI Conference 2013 Conference Paper

Parameterized Complexity of Optimal Planning: A Detailed Map

  • Martin Kronegger
  • Andreas Pfandler
  • Reinhard Pichler

The goal of this paper is a systematic parameterized complexity analysis of different variants of propositional STRIPS planning. We identify several natural problem parameters and study all possible combinations of 9 parameters in 6 different settings. These settings arise, for instance, from the distinction if negative effects of actions are allowed or not. We provide a complete picture by establishing for each case either paraNPhardness (i. e. , the parameter combination does not help) or W[t]-completeness with t ∈ {1, 2} (i. e. , fixed-parameter intractability), or FPT (i. e. , fixedparameter tractability).

PDF Details DOI

ECAI Conference 2012 Conference Paper

Fixed-Parameter Algorithms for Closed World Reasoning

  • Martin Lackner
  • Andreas Pfandler

Closed world reasoning and circumscription are essential tasks in AI. However, their high computational complexity is a serious obstacle for their practical application. In this work we employ the framework of parameterized complexity theory in order to search for fixed-parameter algorithms. We consider eleven parameters describing different characteristics of the input. For several combinations of these parameters we are able to design efficient fixedparameter tractable algorithms. All our algorithms have a runtime only single-exponential in the parameters and linear in the input size. Furthermore, by providing parameterized hardness results we show that we have actually found all tractable fragments involving these eleven parameters. We hereby offer a complete picture of the parameterized complexity of brave closed world reasoning and circumscription.

Details

KR Conference 2012 Conference Paper

Fixed-Parameter Algorithms for Finding Minimal Models

  • Martin Lackner
  • Andreas Pfandler

Computing minimal models is an important task in Knowledge Representation and Reasoning that appears in formalisms such as circumscription, diagnosis and answer set programming. Even the most basic question of whether there exists a minimal model containing a given variable is known to be ΣP 2 -complete. In this work we study the problem of computing minimal models from the viewpoint of parameterized complexity theory. We perform an extensive complexity analysis of this problem with respect to eleven parameters. Tractable fragments based on combinations of these parameters are identified by giving several fixedparameter algorithms. For the remaining combinations we show parameterized hardness results and thus prove that under usual complexity theoretic assumptions no further fixed-parameter algorithms exist for these parameters.

AAAI Conference 2012 Conference Paper

The Parameterized Complexity of Abduction

  • Michael Fellows
  • Andreas Pfandler
  • Frances Rosamond
  • Stefan Rümmele

Abduction belongs to the most fundamental reasoning methods. It is a method for reverse inference, this means one is interested in explaining observed behavior by finding appropriate causes. We study logic-based abduction, where knowledge is represented by propositional formulas. The computational complexity of this problem is highly intractable in many interesting settings. In this work we therefore present an extensive parameterized complexity analysis of abduction within various fragments of propositional logic together with (combinations of) natural parameters.

PDF Details
v2026.09.13