Proceedings

• A. Bernstein, S. Hölldobler, G. Hotz, K.-P. Löhr, P. Molitor, G. Neumann, R. Reischuk, D. Saupe, M. Spiliopoulou, H. Störrle, D. Wagner::
  Ausgezeichnete Informatikdissertationen 2011.
  Volume D-12 of Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2012.

Journal articles

• Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau:
  Smoothed Analysis of Left-To-Right Maxima with Applications.
  ACM Transactions on Algorithms, 8(3):Article No. 30, 2012.
  Go to website | Show abstract
  
  A left-to-right maximum in a sequence of n numbers s1, …, sn is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of n numbers si ? [0,1] that are perturbed by uniform noise from the interval [-?,?], the expected number of left-to-right maxima is ?(&sqrt;n/? + log n) for ?>1/n. For Gaussian noise with standard deviation ? we obtain a bound of O((log3/2 n)/? + log n). We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of ?(&sqrt;n/? + log n) and ?(n/?+1&sqrt;n/? + n log n), respectively, for uniform random noise from the interval [-?,?]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to smoothed motion complexity, a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in d-dimensional space.
• Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, Roded Sharan:
  Approximation Algorithms for Orienting Mixed Graphs.
  Theoretical Computer Science, 2012 (to appear).
  Show PDF | Go to website | Show abstract
  
  Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Given a graph and a list of source–target vertex pairs, one wishes to assign directions to the edges so as to maximize the number of pairs that admit a directed source-to-target path. When the input graph is undirected, a sub-logarithmic approximation is known for this problem. However, the approximability of the biologically-relevant variant, in which the input graph has both directed and undirected edges, was left open. Here we give the first approximation algorithms to this problem. Our algorithms provide a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.
• Michael Elberfeld, Ilka Schnoor, Till Tantau:
  Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
  Theoretical Computer Science, 432:38–51, 2012.
  Show PDF | Go to website | Show abstract
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing, which is often the case in laboratory data, the resulting formal problem IPPH, which stands for incomplete perfect phylogeny haplotyping, is NP-complete. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP-complete; but here, at least, a fixed-parameter algorithm is known. Such drastic and ad hoc simplifications turn out to be unnecessary to make IPPH tractable: we present the first theoretical analysis of a parametrized algorithm, which we develop in the course of the paper, that works for arbitrary instances of IPPH. This tractability result is optimal insofar as we prove IPPH to be NP-complete whenever any of the parameters we consider is not fixed, but part of the input.
• Michael Elberfeld, Till Tantau:
  Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  Information and Computation, 213:33–47, 2012.
  Show PDF | Go to website | Show abstract
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption.
• Maciej Liskiewicz, Martin R. Schuster:
  Improved Analysis of an Exact Algorithm for Cubic Graph TSP.
  CoRR, (abs/1207.4694)2012.
  Go to website
• Johannes Textor, Maciej Liskiewicz:
  Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective.
  CoRR, (abs/1202.3764)2012.
  Go to website

Conference papers

• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
  In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), Volume 14 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 66-77. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
  Show PDF | Go to website | Show abstract
  
  An algorithmic meta theorem for a logic and a class C of structures states that all problems ex- pressible in this logic can be solved efficiently for inputs from C. The prime example is Courcelle’s Theorem, which states that monadic second-order (mso) definable problems are linear-time solv- able on graphs of bounded tree width. We contribute new algorithmic meta theorems, which state that mso-definable problems are (a) solvable by uniform constant-depth circuit families (AC0 for decision problems and TC0 for counting problems) when restricted to input structures of bounded tree depth and (b) solvable by uniform logarithmic-depth circuit families (NC1 for decision prob- lems and #NC1 for counting problems) when a tree decomposition of bounded width in term representation is part of the input. Applications of our theorems include a TC0-completeness proof for the unary version of integer linear programming with a fixed number of equations and extensions of a recent result that counting the number of accepting paths of a visible pushdown automaton lies in #NC1. Our main technical contributions are a new tree automata model for unordered, unranked, labeled trees; a method for representing the tree automata’s computations algebraically using convolution circuits; and a lemma on computing balanced width-3 tree de- compositions of trees in TC0, which encapsulates most of the technical difficulties surrounding earlier results connecting tree automata and NC1.
• Michael Elberfeld, Christoph Stockhusen, Till Tantau:
  On the Space Complexity of Parameterized Problems.
  In Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), Volume 7535 of Lecture Notes in Computer Science, pp. 206-217. Springer, 2012.
  Go to website | Show abstract
  
  Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. We show that the undirected and the directed feedback vertex set problems have different parameterized space complexities, unless L = NL; which explains why the two problem variants seem to necessitate different algorithmic approaches even though their parameterized time complexity is the same. For a number of further natural parameterized problems, including the longest common subsequence problem and the acceptance problem for multi-head automata, we show that they lie in or are complete for different parameterized space classes; which explains why previous attempts at proving completeness of these problems for parameterized time classes have failed.
• Michael Elberfeld, Martin Grohe, Till Tantau:
  Where First-Order and Monadic Second-Order Logic Coincide.
  In Proceedings of the 27th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2012), pp. 265-274. IEEE Computer Society, 2012.
  Show PDF | Go to website | Show abstract
  
  We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for each class of graphs that is closed under taking subgraphs, FO and MSO have the same expressive power on the class if, and only if, it has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking induced subgraphs, we show an analogous result for guarded second-order logic (GSO), the variant of MSO that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman-Vaught-type theorem that is constructive and still works for unbounded partitions.

Technical reports

• Michael Elberfeld, Christoph Stockhusen, Till Tantau:
  On the Space Complexity of Parameterized Problems.
  Technical report , ECCC, 2012.
  Go to website | Show PDF | Show abstract
  
  Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. We show that the undirected and the directed feedback vertex set problems have different parameterized space complexities, unless L=NL. For a number of further natural parameterized problems, including the longest common subsequence problem, the acceptance problem for multi-head automata, and the associative generability problem we show that they lie in or are complete for different parameterized space classes. Our results explain why previous attempts at proving completeness of different problems for parameterized time classes have failed.

PhD theses

• Michael Elberfeld:
  Space and Circuit Complexity of Monadic Second-Order Definable Problems on Tree-Decomposable Structures.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Till Tantau, Heribert Vollmer, Rolf Niedermeier.
  Show PDF | Show abstract
  
  A famous theorem of Courcelle states that every problem that is definable in monadic second-order (MSO) logic can be solved in linear time on input structures of bounded tree width. While Courcelle’s result is optimal from the algorithmic point of view, this thesis shows how to solve monadic second- order definable decision, counting, and optimization problems on tree-width-bounded structures optimally from the complexity theoretic point of view. Beside bounded tree width, the related notion of bounded tree depth is considered.
  
  A first set of results covers input structures of bounded tree width, which admit tree decompositions of bounded width. It is shown that all MSO-definable decision, counting, and optimization problems are solvable in deterministic logarithmic space (logspace) in this setting. Transferring the powerful framework of MSO-definability to logspace allows one to settle the complexity of problems related to finding paths and matchings in graphs: It is shown that answering reachability queries and counting the number of perfect matchings in graphs of bounded tree width can be done in logspace. Moreover, by solving problems on tree-width-bounded graphs as subroutines, problems on inputs of unbounded tree width are solvable in logspace; like deciding whether undirected loop-free graphs have cycles whose length is a multiple of any constant. These results rest on the new technique of constructing width-bounded tree decompositions in logspace.
  
  Once tree decompositions are available, a task shown to be complete for logspace, actually solving MSO-definable decision and counting problems can be done by logarithmic-depth Boolean and arithmetic circuits, respectively. This finding itself unifies many automaton evaluation tasks studied in the area of logarithmic-depth circuits in an elegant manner using MSO-formulæ. To let logarithmic-depth circuits work on tree decompositions whose underlying trees have arbitrary depth, a preprocessing step is used that balances them using constant-depth threshold circuits.
  
  The second set of results spans input structures of bounded tree depth, which admit tree decompositions of bounded width whose underlying trees have bounded depth. The logspace results are transferred to this setting to solve MSO-definable decision, counting, and optimization problems by constant-depth Boolean, arithmetic, and threshold circuits, respectively. These theorems apply to number problems like solving systems of any constant number of linear equations whose coefficients are given in unary. For their proofs input structures are turned into trees of bounded depth and unbounded degree. Translating MSO-formulæ to just the right automaton model for this situation and representing automata computations algebraically by arithmetic circuits lies at the heart of the proofs of these results.
  
  In terms of computational power, constant-depth circuits are equivalent to first-order formulæ that have access to ordering and arithmetic predicates defined on the input’s universe. It is shown that these build-in predicates are not needed to evaluate MSO-formulæ once input structures are extracted from their string encodings: First-order formulæ and MSO-formulæ define the same problems on any class of structures of bounded tree depth. The main building block in the proof of this result is a new constructive Feferman–Vaught-type composition theorem for unbounded partitions.

Masters theses

• Y. B.:
  Sichere Zwei-Parteien Protokolle zur Berechnung von Entscheidungsbäumen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Maciej Liskiewicz, Rüdiger Reischuk.
• S. K.:
  Data-based Projection Access Order for SART.
  Universität zu Lübeck, Institut für Medizintechnik, 2012.
  Supervised by: Thorsten M. Buzug, Till Tantau.
• C. P.:
  DSL-based Runtime Verification for the JVM.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
  Supervised by: Martin Leucker, Rüdiger Reischuk.
• C. S.:
  Digital Camera Identification.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Rüdiger Reischuk, Maciej Liskiewicz.
• M. S.:
  Exact Algorithms for Traveling Salesman Problem in Cubic Graphs.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Maciej Liskiewicz, Martin Leucker.
• N. T.:
  Dekomposition von Bäumen und Termin in AC0 und TC0.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Till Tantau, Maciej Liskiewicz.

Bachelors theses

• M. B.:
  Berechnungskomplexitäten von Varianten des Subset-Sum-Problems.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Till Tantau, Hans-Martin Teichert.
  Show PDF | Show abstract
  
  In this thesis we take a look at the problem subsetsum, in which a subset out of a set of natural numbers must be chosen in a way, that the sum of these elements equals a given number. A lot of natural pro- blems can be reduced to subsetsum because of the simple structure of the problem, therefore the complexity of subsetsum is interesting for computer science. In this thesis we will analyze a few versions of subsetsum because all these versions are NP complete if we consider a default binary encoding, but a few of them lie in different complexity classes if we consider them with a unary encoding. In this thesis we will study a few natural versions of the problem and examine them in this regard and present the results.
• M. B.:
  Multimengen-Baumautomaten: Analyse und Implementierung.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Till Tantau, Martin Leucker.
• S. G.:
  Eine Multicommodity Push-Relabel-Algorithmus und Anwendung für parametrisierte Graphen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Rüdiger Reischuk, Maciej Liskiewicz.
• P. H.:
  Turn Costs in Energy-Optimal Route Planning for Electric Vehicles.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
  Supervised by: Martin Leucker, Maciej Liskiewicz.
• C. K.:
  Algorithmen und Datenstrukturen für Prioritätswarteschlangen auf partiellen Ordnungen.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
  Supervised by: Martin Leucker, Maciej Liskiewicz.
• I. K.:
  Lösungsstrategien und semiautomatische Generierung von Testdatensätzen bei ACM-ICPC-artigen Graphproblemen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Maciej Liskiewicz, Till Tantau.
• S. M.:
  Implementation and Comparison of Algorithms for Constructing and Visualizing Phylogenetic Trees.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Till Tantau, Hans-Martin Teichert.
  Show PDF | Show abstract
  
  TEX is a typesetting system which is frequently used for scientific docu- ments. The TEX package TikZ allows for the creation of high quality vector graphics directly from a TEX document. The aim of this thesis was to ex- pand the TikZ graph drawing library, in order to enable the computation and visualization of phylogenetic trees. Phylogenetic trees are diagrams that display the phylogeny of a set of taxa in a tree-like manner. One type of approach on determining the evolutionary history of a dataset are the distance-based methods, where the phylogeny is estimated on the basis of a distance matrix. There are a number of different distance-based methods, of which two are dealt with here: the UPGMA and the BME algorithm. While the former has the advantage of being simple and thus easy to implement, the latter is superior when it comes to topological accuracy, time complexity, and applicability. As both these algorithms do not only determine the tree’s topology, but also the respective edge lengths, a graph drawing algorithm, which can handle fixed edge lengths, is also nec- essary. Both the phylogenetic tree and the graph drawing algorithms have been implemented in the programming language Lua, as LuaTEX delivers the possibility of incorporating Lua-code directly into TEX. The algorithms and their implementation will be discussed and compared, whereas the im- plemented module is used for the exemplary computation and visualization of phylogenetic trees directly in this document.
• M. S.:
  Transformation von regulärer Linearzeit-Temporallogik zu Paritätsautomaten.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
  Supervised by: Martin Leucker, Till Tantau.
• B. W.:
  Steganographie in Binärbildern.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Maciej Liskiewicz, Rüdiger Reischuk.
• F. W.:
  Synchronisierungsmethoden zur Huffmankodierung.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Supervised by: Maciej Liskiewicz, Andreas Schrader.