Editorium

• 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.
  Band D-12 von Lecture Notes in Informatics, Dissertationen, Gesellschaft für Informatik, 2012.

Zeitschriftenartikel

• 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.
  Website anzeigen | Zusammenfassung anzeigen
  
  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 (noch nicht erschienen).
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  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.
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  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.
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  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.
  Website anzeigen
• Johannes Textor, Maciej Liskiewicz:
  Adjustment Criteria in Causal Diagrams: An Algorithmic Perspective.
  CoRR, (abs/1202.3764)2012.
  Website anzeigen

Konferenzbeiträge

• 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), Band 14 von Leibniz International Proceedings in Informatics (LIPIcs), S. 66-77. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2012.
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  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), Band 7535 von Lecture Notes in Computer Science, S. 206-217. Springer, 2012.
  Website anzeigen | Zusammenfassung anzeigen
  
  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), S. 265-274. IEEE Computer Society, 2012.
  PDF anzeigen | Website anzeigen | Zusammenfassung anzeigen
  
  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.

Technische Berichte

• Michael Elberfeld, Christoph Stockhusen, Till Tantau:
  On the Space Complexity of Parameterized Problems.
  Technischer Bericht , ECCC, 2012.
  Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  
  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.

Dissertationen

• 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.
  Gutachter: Till Tantau, Heribert Vollmer, Rolf Niedermeier.
  PDF anzeigen | Zusammenfassung anzeigen
  
  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.

Master- und Diplomarbeiten

• Y. B.:
  Sichere Zwei-Parteien Protokolle zur Berechnung von Entscheidungsbäumen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Gutachter: Maciej Liskiewicz, Rüdiger Reischuk.
• S. K.:
  Data-based Projection Access Order for SART.
  Universität zu Lübeck, Institut für Medizintechnik, 2012.
  Gutachter: 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.
  Gutachter: Martin Leucker, Rüdiger Reischuk.
• C. S.:
  Digital Camera Identification.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Gutachter: 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.
  Gutachter: 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.
  Gutachter: Till Tantau, Maciej Liskiewicz.

Bachelor- und Studienarbeiten

• M. B.:
  Berechnungskomplexitäten von Varianten des Subset-Sum-Problems.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Gutachter: Till Tantau, Hans-Martin Teichert.
  PDF anzeigen | Zusammenfassung anzeigen
  
  In dieser Arbeit betrachten wir das Problem subsetsum, bei dem aus ei- ner gegebenen Menge von natürlichen Zahlen eine Teilmenge bestimmt werden soll, sodass die Elemente dieser Teilmenge in der Summe ei- ne vorgegebene Zahl ergeben. Die Komplexität von subsetsum ist für die Informatik interessant, denn aufgrund des generischen Aufbaus von subsetsum lassen sich viele weitere Probleme darauf zurückfüh- ren. In dieser Arbeit soll die Komplexität von mehreren Varianten von subsetsum untersucht werden, denn obwohl fast alle Varianten des Pro- blems in der üblichen binären Codierung NP-vollständig sind, haben diese Probleme oft unterschiedliche Komplexitäten, wenn wir unäre Kodierungen betrachten. In dieser Arbeit werden einige natürliche Va- rianten dieses Problems diesbezüglich untersucht und entsprechende Resultate präsentiert.
• M. B.:
  Multimengen-Baumautomaten: Analyse und Implementierung.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Gutachter: 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.
  Gutachter: 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.
  Gutachter: 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.
  Gutachter: 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.
  Gutachter: 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.
  Gutachter: Till Tantau, Hans-Martin Teichert.
  PDF anzeigen | Zusammenfassung anzeigen
  
  TEX ist ein Textsatzsystem, das häufig für die Erstellung wissenschaftli- cher Dokumente eingesetzt wird. Das TEX-Paket TikZ ermöglicht zusätz- lich die Erzeugung von qualitativ hochwertigen Vektorgraphiken direkt in einem TEX-Dokument. Das Ziel dieser Arbeit war es, die TikZ-Graph-Draw- ing-Bibliothek so zu erweitern, dass die Berechnung und Visualisierung phy- logenetischer Bäume ebenfalls möglich wird. Phylogenetische Bäume sind Diagramme, die die Phylogenie einer Men- ge an Taxa in einer baumartigen Struktur darstellt. Die Stammesgeschichte kann z.B. durch die sogenannten distance-based methods (engl. distanzbasierte Methoden) berechnet werden, wobei die Phylogenie anhand einer Distanz- matrix abgeschätzt wird. Es gibt verschiedene distanzbasierte Ansätze, von denen zwei in dieser Arbeit näher betrachtet werden: der UPGMA- und der BME-Algorithmus. Während UPGMA eher einfach und dadurch auch leicht zu implementieren ist, ist BME deutlich überlegen, wenn es um akkurate Topologie, Zeitkomplexität und Einsetzbarkeit geht. Da die beiden Algo- rithmen nicht nur die Topologie des Baumes, sondern auch dessen Kan- tenlängen bestimmen, ist auch ein Algorithmus erforderlich, der mit dem Zeichnen von Graphen mit festen Kantenlängen umgehen kann. Sowohl die Algorithmen für die Berechnung phylogenetischer Bäume als auch die für deren Zeichnung wurden in der Programmiersprache Lua implementiert, da es LuaTEX ermöglicht, Lua-Code direkt in TEX einzubetten. Die Algorithmen und ihre Implementierungen werden diskutiert und verglichen, wobei das implementierte Modul für die Berechnung und Visualisierung einiger bei- spielhafter phylogenetischer Bäume direkt in diesem Dokument angewandt wird.
• M. S.:
  Transformation von regulärer Linearzeit-Temporallogik zu Paritätsautomaten.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2012.
  Gutachter: Martin Leucker, Till Tantau.
• B. W.:
  Steganographie in Binärbildern.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Gutachter: Maciej Liskiewicz, Rüdiger Reischuk.
• F. W.:
  Synchronisierungsmethoden zur Huffmankodierung.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2012.
  Gutachter: Maciej Liskiewicz, Andreas Schrader.