Fixed-Parameter 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^P-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 fixed-parameter 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.
A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs
With Marie-Louise Bruner
13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012)
The NP-complete Permutation Pattern Matching problem asks whether a permutation P can be matched into a permutation T. A matching is an order-preserving embedding of P into T. We present a fixed-parameter algorithm solving this problem with an exponential worst-case runtime of O*(1.79run(T)), where run(T) denotes the number of alternating runs of T. This is the first algorithm that improves upon the O*(2n) runtime required by brute-force search without imposing restrictions on P and T. Furthermore we prove that - under standard complexity theoretic assumptions - such a fixed-parameter tractability result is not possible for run(P).
Multicut on Graphs of Bounded Clique-width
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 NP-complete. The goal of our work is to investigate the potential of clique-width for identifying tractable fragments of Multicut. We show for several parameterizations involving clique-width whether they lead to tractability or not. Since bounded tree-width implies bounded clique-width, our tractability results extend previous results via tree-width, in particular to dense graphs.
Fixed-Parameter 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 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 fixed-parameter 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.
The Complexity of Nearly Single-Peaked Consistency
With Gábor Erdélyi and Andreas Pfandler
Fourth International Workshop on Computational Social Choice (COMSOC 2012))
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 problems suddenly become easy to solve. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra 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 in many cases NP-complete. Furthermore, we explore the relations between several notions of nearly single-peakedness.
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 NP-complete. 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 Marie-Louise 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.