Skip to Content

Path: DBAI > staff > Martin Lackner

Tools: Drucken

Short CV

Research interests

• Algorithms, especially parameterized algorithms
• Computational social choice
• Computational aspects of permutation problems
• Logic in Artificial Intelligence, especially Reasoning

Publications

• Computational Aspects of Nearly Single-Peaked Electorates

  With Gábor Erdélyi and Andreas Pfandler
  to appear at the Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2013)
  (A preliminary version appeared at the 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 systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra (2011) 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 single-peakedness.
  > PDF (short version), Arxiv (extended version)

• The computational landscape of permutation patterns

  With Marie-Louise 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.
  > Arxiv

• 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.
  > AAAI Press, PDF, Slides, BibTex

• 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.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ⁿ) 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).
  > Springer, Arxiv (extended version), Slides, BibTex

• 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.
  > Springer, PDF (Preprint), Slides, BibTex

• 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.
  > IOS Press, PDF (Preprint), BibTex

• 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.
  > PDF, Slides, BibTex

• 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.
  > Springer, PDF (Preprint), BibTex

• 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.
  > PDF

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Informationssysteme an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. / Disclaimer.