I am research assistant at the Database and Artificial Intelligence Group at the Vienna Technnical University of Technology.
I am also a PhD student in the Doctoral Programme

Computational Aspects of Nearly SinglePeaked Electorates
With Gábor Erdélyi and Andreas Pfandler
to appear at the TwentySeventh AAAI Conference on Artificial Intelligence (AAAI 2013)
(A preliminary version appeared at COMSOC 2012)
Manipulation, bribery, and control are wellstudied 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 singlepeaked electorates, these systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra (2011) studied the complexity of dishonest behavior in nearly singlepeaked electorates. These are electorates that are not singlepeaked but close to it according to some distance measure.
In this paper we introduce several new distance measures regarding singlepeakedness. We prove that determining whether a given profile is nearly singlepeaked is NPcomplete in many cases. For one case we present a polynomialtime algorithm. Furthermore, we explore the relations between several notions of nearly singlepeakedness.

Incomplete Preferences in SinglePeaked Electorates
to appear at the 7th Multidisciplinary Workshop on Advances in Preference Handling (MPREF 2013)
Incomplete preferences are likely to arise in realworld preference aggregation and voting systems.
This paper deals with determining whether an incomplete preference profile is singlepeaked.
This is essential information since many intractable voting problems become tractable for singlepeaked profiles.
We prove that for incomplete profiles the problem of determining singlepeakedness is NPcomplete.
Despite this computational hardness result, we find two polynomialtime algorithms for reasonably restricted settings.

A Parameterized Complexity Analysis of Generalized CPNets
With Martin Kronegger, Andreas Pfandler and Reinhard Pichler
to appear at the 7th Multidisciplinary Workshop on Advances in Preference Handling (MPREF 2013)
Generalized CPnets (GCPnets) allow a succinct representation of preferences over multiattribute domains.
As a consequence of their succinct representation, many GCPnet related tasks are computationally hard.
Even finding the more preferable of two outcomes is PSPACEcomplete.
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 GCPnets.
Second, we search for efficient fixedparameter tractable algorithms.

The computational landscape of permutation patterns
With MarieLouise Bruner
to appear in Pure Mathematics and Applications
In the last years, different types of patterns in permutations have been studied: vincular, bivincular and mesh patterns, just to name a few. Every type of permutation pattern naturally defines a corresponding computational problem: Given a pattern P and a permutation T (the text), is P contained in T? In this paper we draw a map of the computational landscape of permutation pattern matching with different types of patterns. We provide a classical complexity analysis and investigate the impact of the pattern length on the computational hardness. Furthermore, we highlight several directions in which the study of computational aspects of permutation patterns could evolve.

FixedParameter Algorithms for Finding Minimal Models
With Andreas Pfandler
13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012)
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 Σ_2^Pcomplete. 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 fixedparameter algorithms exist for these parameters.

A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
With MarieLouise Bruner
13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012)
The NPcomplete Permutation Pattern Matching problem asks whether a permutation P can be matched into a permutation T. A matching is an orderpreserving embedding of P into T. We present a fixedparameter algorithm solving this problem with an exponential worstcase runtime of O*(1.79^{run(T)}), where run(T) denotes the number of alternating runs of T. This is the first algorithm that improves upon the O*(2^{n}) runtime required by bruteforce search without imposing restrictions on P and T. Furthermore we prove that  under standard complexity theoretic assumptions  such a fixedparameter tractability result is not possible for run(P).

Multicut on Graphs of Bounded Cliquewidth
With Reinhard Pichler, Stefan Rümmele and Stefan Woltran
6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012)
Several variants of Multicut problems arise in applications like circuit and network design. In general, these problems are NPcomplete. The goal of our work is to investigate the potential of cliquewidth for identifying tractable fragments of Multicut. We show for several parameterizations involving cliquewidth whether they lead to tractability or not. Since bounded treewidth implies bounded cliquewidth, our tractability results extend previous results via treewidth, in particular to dense graphs.

FixedParameter Algorithms for Closed World Reasoning
With Andreas Pfandler
20th European Conference on Artificial Intelligence (ECAI 2012)
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 fixedparameter 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 singleexponential 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.

The Complexity of Nearly SinglePeaked Consistency
With Gábor Erdélyi and Andreas Pfandler
Fourth International Workshop on Computational Social Choice (COMSOC 2012))
Manipulation, bribery, and control are wellstudied 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 singlepeaked electorates, these problems suddenly become easy to solve. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the complexity of dishonest behavior in nearly singlepeaked electorates. These are electorates that are not singlepeaked but close to it according to some distance measure.
In this paper we introduce several new distance measures regarding singlepeakedness. We prove that determining whether a given profile is nearly singlepeaked is in many cases NPcomplete. Furthermore, we explore the relations between several notions of nearly singlepeakedness.

Train Marshalling Is Fixed Parameter Tractable
With Leo Brueggeman, Michael Fellows, Rudolf Fleischer, Christian Komusiewicz, Yiannis Koutis, Andreas Pfandler and Frances Rosamond
Sixth International Conference on Fun with Algorithms (FUN 2012)
The train marshalling problem is about reordering the cars of a train using as few auxiliary rails as possible. The problem is known to be NPcomplete. We show that it is fixed parameter tractable (FPT) with the number of auxiliary rails as parameter.

From Peaks to Valleys, Running Up and Down: Fast Permutation Pattern Matching
With MarieLouise Bruner
Tiny Transactions on Computer Science (TinyTOCS)
This paper aims to explain our results in "A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs" with only 140 characters. This radical length constraint is the central idea of the Tiny Transactions on Computer Science journal.