Editorium

• Rüdiger Reischuk, Steffen Höllendobler, et al.:
  Ausgezeichnete Informatikdissertationen 2018.
  Lecture Notes in Informatic Dissertation, GI-Edition, 2019.

Buchbeiträge

• Max Bannach:
  Parallele Parametrisierte Algorithmen.
  In Ausgezeichnete Informatikdissertationen 2019, Band D-20 von LNI, S. 29--38. GI, 2019.
  Website anzeigen | Zusammenfassung anzeigen
  
  Die parametrisierte Algorithmik ist ein Schlüsselbereich des modernen Algorithmenentwurfes sowie der Komplexitätstheorie. Die fast ausschließlich untersuchte Ressource in diesem Bereich ist dabei die sequentielle Zeit, obwohl die Parallelverarbeitung ein zentrales und vielfach untersuchtes Teilgebiet der klassischen Algorithmik ist. Sowohl das Identifizieren eines geeigneten Parameters als auch die direkte Beschleunigung durch Parallelisierung verfolgen das gleiche Ziel: möglichst viele Instanzen eines an sich nicht effizient lösbaren Problems dennoch zu lösen. Es ist daher naheliegend, beide Forschungsgebiete miteinander zu verbinden – und genau diese Art von Integration ist das Ziel dieser Arbeit. Ich präsentiere eine Vielzahl von parametrisierten Komplexitätsklassen und entwickle eine Sammlung von parallelen parametrisierten Basisalgorithmen. Dabei werden nahezu alle Techniken, die die parametrisierte Komplexitätstheorie zu bieten hat, von einem parallelen Standpunkt aus untersucht – unter anderem Color Coding, beschränkte Suchbäume, Kernelisierung, strukturelle Zerlegungen von Graphen sowie algorithmische Metasätze. Außerdem illustriere ich, wie die letzten zwei Techniken in der Praxis genutzt werden können, indem ich zwei Software-Bibliotheken vorstelle: eine zum Berechnen optimaler Baumzerlegungen und eine für die Modellprüfung eines Fragmentes der monadischen Prädikatenlogik zweiter Stufe.

Zeitschriftenartikel

• Max Bannach, Sebastian Berndt:
  Practical Access to Dynamic Programming on Tree Decompositions.
  MDPI Algorithms, 2019. Special Issue: New Frontiers in Parameterized Complexity and Algorithms
  Website anzeigen | Zusammenfassung anzeigen
  
  Parameterized complexity theory has led to a wide range of algorithmic breakthroughs within the last few decades, but the practicability of these methods for real-world problems is still not well understood. We investigate the practicability of one of the fundamental approaches of this field: dynamic programming on tree decompositions. Indisputably, this is a key technique in parameterized algorithms and modern algorithm design. Despite the enormous impact of this approach in theory, it still has very little influence on practical implementations. The reasons for this phenomenon are manifold. One of them is the simple fact that such an implementation requires a long chain of non-trivial tasks (as computing the decomposition, preparing it, …). We provide an easy way to implement such dynamic programs that only requires the definition of the update rules. With this interface, dynamic programs for various problems, such as 3-coloring, can be implemented easily in about 100 lines of structured Java code. The theoretical foundation of the success of dynamic programming on tree decompositions is well understood due to Courcelle’s celebrated theorem, which states that every MSO-definable problem can be efficiently solved if a tree decomposition of small width is given. We seek to provide practical access to this theorem as well, by presenting a lightweight model checker for a small fragment of MSO1 (that is, we do not consider “edge-set-based” problems). This fragment is powerful enough to describe many natural problems, and our model checker turns out to be very competitive against similar state-of-the-art tools.
• Katharina Dannenberg, Jesper Jansson, Andrzej Lingas, Eva-Marta Lundell:
  The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets.
  Discrete Applied Mathematics, 257:101-114, 2019.
  Website anzeigen
• Tom Hartmann, Max Bannach, Martin Middendorf:
  Sorting Signed Permutations by Inverse Tandem Duplication Random Losses.
  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2019.
  Website anzeigen | Zusammenfassung anzeigen
  
  Gene order evolution of unichromosomal genomes, for example mitochondrial genomes, has been modelled mostly by four major types of genome rearrangements: inversions, transpositions, inverse transpositions, and tandem duplication random losses. Generalizing models that include all those rearrangements while admitting computational tractability are rare. In this paper we study such a rearrangement model, namely the inverse tandem duplication random loss (iTDRL) model, where an iTDRL duplicates and inverts a continuous segment of a gene order followed by the random loss of one of the redundant copies of each gene. The iTDRL rearrangement has currently been proposed by several authors suggesting it to be a possible mechanisms of mitochondrial gene order evolution. We initiate the algorithmic study of this new model of genome rearrangement by proving that a shortest rearrangement scenario that transforms one given gene order into another given gene order can be obtained in quasilinear time. Furthermore, we show that the length of such a scenario, i. e., the minimum number of iTDRLs in the transformation, can be computed in linear time.
• Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
  Proper learning of k-term DNF formulas from satisfying assignments.
  Journal of Computer and System Sciences, 106:129-144, 2019.
  Website anzeigen | Zusammenfassung anzeigen
  
  In certain applications there may be only positive examples available to learn concepts of a class of interest. Furthermore, learning has to be done properly, i.e. the hypothesis space has to coincide with the concept class, and without false positives, i.e. the hypothesis always has to be a subset of the real concept (one-sided error). For the well studied class of k-term DNF formulas it has been known that learning is difficult. Unless RP=NP, it is not feasible to learn k-term DNF formulas properly in a distribution-free sense even if both positive and negative examples are available and even if false positives are allowed. This paper constructs an efficient algorithm that, for fixed but arbitrary k and q, if examples are drawn from q-bounded distributions, it properly learns the class of k-term DNFs without false positives from positive examples alone with arbitrarily small relative error.
• Benito van der Zander, Maciej Liskiewicz, Johannes Textor:
  Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework.
  Artificial Intelligence, Vol. 270, Pages 1-40, (270):1-40, 2019.
  Website anzeigen

Konferenzbeiträge

• Max Bannach, Till Tantau:
  On the Descriptive Complexity of Color Coding.
  In Proceedings of STACS 2019, LIPIcs, LIPIcs, 2019.
  Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  
  Color coding is an algorithmic technique used in parameterized complexity theory to detect ``small'' structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing -- purely in terms of the syntactic structure of describing formulas -- when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in FPT just because of the way they are commonly described using logical formulas.
• Max Bannach, Sebastian Berndt:
  Positive-Instance Driven Dynamic Programming for Graph Searching.
  In Proceedings of the 16th Algorithms and Data Structures Symposium (WADS 2019), Springer, 2019.
  PDF anzeigen | Zusammenfassung anzeigen
  
  Research on the similarity of a graph to being a tree – called the treewidth of the graph – has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic program- ming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Al- gorithms producing only such subinstances are called positive-instance driven (PID). We give an alternative and intuitive view on this algo- rithm from the perspective of the corresponding configuration graphs in certain two-player games. This allows us to develop PID-algorithms for a wide range of important graph parameters such as treewidth, pathwidth, q-branched treewidth, treedepth and dependency-treewidth. We analyze the worst case behavior of the approach on some well-known graph classes and perform an experimental evaluation on real world and random graphs.
• Max Bannach, Malte Skambath, Till Tantau:
  Towards Work-Efficient Parallel Parameterized Algorithms.
  In Proceedings of the 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019), Springer, 2019.
  Website anzeigen | PDF anzeigen | Zusammenfassung anzeigen
  
  Parallel parameterized complexity theory studies how fixed-parameter tractable (fpt) problems can be solved in parallel. Previous theoretical work focused on parallel algorithms that are very fast in principle, but did not take into account that when we only have a small number of processors (between 2 and, say, 1024), it is more important that the parallel algorithms are work-efficient. In the present paper we investigate how work-efficient fpt algorithms can be designed. We review standard methods from fpt theory, like kernelization, search trees, and interleaving, and prove trade-offs for them between work efficiency and runtime improvements. This results in a toolbox for developing work-efficient parallel fpt algorithms.
• Tom Hartmann, Max Bannach, Martin Middendorf:
  Sorting Signed Permutations by Inverse Tandem Duplication Random Losses.
  In Proceedings of the 17th Asia Pacific Bioinformatics Conference (APBC 2019), , 2019.
  PDF anzeigen | Zusammenfassung anzeigen
  
  Gene order evolution of unichromosomal genomes, for example mitochondrial genomes, has been modelled mostly by four major types of genome rearrangements: inversions, transpositions, inverse transpositions, and tandem duplication random losses. Generalizing models that include all those rearrangements while admitting computational tractability are rare. In this paper we study such a rearrangement model, namely the inverse tandem duplication random loss (iTDRL) model, where an iTDRL duplicates and inverts a continuous segment of a gene order followed by the random loss of one of the redundant copies of each gene. The iTDRL rearrangement has currently been proposed by several authors suggesting it to be a possible mechanisms of mitochondrial gene order evolution. We initiate the algorithmic study of this new model of genome rearrangement on signed permutations by proving that a shortest rearrangement scenario that transforms one given gene order into another given gene order can be obtained in quasilinear time. Furthermore, we show that the length of such a scenario, i. e., the minimum number of iTDRLs in the transformation, can be computed in linear time.
• Zacharias Heinrich, Rüdiger Reischuk:
  Improved Dynamic Kernels for Hitting-Set.
  In 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, S. 69-72. Inproceedings, 2019.
  PDF anzeigen
• Florian Thaeter:
  Hardness of k-anonymous microaggregation.
  In 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, S. 135-138. Inproceedings, 2019.
  PDF anzeigen
• Benito van der Zander, Maciej Liskiewicz:
  Finding minimal d-separators in linear time and applications.
  In Proceedings of the 35th Conference on Uncertainty in Artificial Intelligence (UAI'19), AUAI Press, 2019.
  PDF anzeigen

Technische Berichte

• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Technischer Bericht , Electronic Colloquium on Computational Complexity, 2019.
  Website anzeigen | Zusammenfassung anzeigen
  
  Computing kernels for the hitting set problem (the problem of finding a size-$k$ set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with $m$ hyperedges, each of size at most~$d$, the best algorithms can compute kernels of size $O(k^d)$ in time $O(2^d m)$. In this paper we generalize the task to the \emph{dynamic} setting where hyperedges may be continuously added and deleted and we always have to keep track of a hitting set kernel (including moments when no size-$k$ hitting set exists). We present a deterministic solution, based on a novel data structure, that needs worst-case time $O^*(3^d)$ for updating the kernel upon hyperedge inserts and time~$O^*(5^d)$ for updates upon deletions -- thus nearly matching the time $O^*(2^d)$ needed by the best static algorithm per hyperedge. As a novel technical feature, our approach does not use the standard replace-sunflowers-by-their-cores methodology, but introduces a generalized concept that is actually easier to compute and that allows us to achieve a kernel size of $\sum_{i=0}^d k^i$ rather than the typical size $d!\cdot k^d$ resulting from the Sunflower Lemma. We also show that our approach extends to the dual problem of finding packings in hypergraphs (the problem of finding $k$ pairwise disjoint hyperedges), albeit with a slightly larger kernel size of $\sum_{i=0}^d d^i(k-1)^i$.

Dissertationen

• Max Bannach:
  Parallel Parameterized Algorithms.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Till Tantau, Heribert Vollmer.
  Website anzeigen | Zusammenfassung anzeigen
  
  Die parametrisierte Algorithmik ist ein Schlüsselbereich des modernen Algorithmenentwurfes sowie der Komplexitätstheorie. Die fast ausschließlich untersuchte Ressource in diesem Bereich ist dabei die sequentielle Zeit, obwohl die Parallelverarbeitung ein zentrales und vielfach untersuchtes Teilgebiet der klassischen Algorithmik ist. Sowohl das Identifizieren eines geeigneten Parameters als auch die direkte Beschleunigung durch Parallelisierung verfolgen das gleiche Ziel: möglichst viele Instanzen eines an sich nicht effizient lösbaren Problems dennoch zu lösen. Es ist daher naheliegend, beide Forschungsgebiete miteinander zu verbinden – und genau diese Art von Integration ist das Ziel dieser Arbeit. Ich präsentiere eine Vielzahl von parametrisierten Komplexitätsklassen und entwickle eine Sammlung von parallelen parametrisierten Basisalgorithmen. Dabei werden nahezu alle Techniken, die die parametrisierte Komplextheorie zu bieten hat, von einem parallelen Standpunkt aus untersucht – unter anderem Color Coding, beschränkte Suchbäume, Kernelisierung, strukturelle Zerlegungen von Graphen sowie algorithmische Metatheoreme. Außerdem illustriere ich, wie die letzten zwei Techniken in der Praxis genutzt werden können, indem ich zwei Software-Bibliotheken vorstelle: eine zum Berechnen optimaler Baumzerlegungen und eine für die Modellprüfung eines Fragmentes der monadischen Prädikatenlogik zweiter Stufe.

Master- und Diplomarbeiten

• Z. H.:
  Dynamische Kernelisierungen für Vertex Cover und Hitting Set.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Rüdiger Reischuk, Till Tantau.
• H. K.:
  Efficient Code Generation for Stream-based Specifications.
  Universität zu Lübeck, Institut für Softwaretechnik und Programmiersprachen, 2019.
  Gutachter: Martin Leucker, Till Tantau.
• C. P.:
  Steganography in Print-Scan Documents.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Rüdiger Reischuk, Thomas Eisenbarth.
• Marcel Wienöbst:
  Constraint-based causal structure learning exploiting low-order conditional independences.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Maciej Liskiewicz, Ralf Möller.
  PDF anzeigen

Bachelor- und Studienarbeiten

• F. G.:
  Algorithms for the Feedback Arc Set Problem.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Rüdiger Reischuk, Heiko Hamann.
• H. H.:
  Aggregation on the shortest path in a Kilobot swarm.
  Universität zu Lübeck, Institut für Technische Informatik, 2019.
  Gutachter: Heiko Hamann, Rüdiger Reischuk.
• F. H.:
  Untersuchungen zur Fixed-Parameter-Tractability des Model-Checking-Problems auf universellen Fragmenten der erststufigen Logik.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Till Tantau, Ralf Möller.
• M. L.:
  Täuschungsstrategien gegen Fingerprinting im Webbrowser.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Maciej Liskiewicz, Thomas Eisenbarth.
• S. M.:
  Der Genetische Code und seine Optimierung statistisch untersucht.
  Universität zu Lübeck, Institut für Neuro- und Bioinformatik, 2019.
  Gutachter: Amir Madany Mamlouk, Till Tantau.
• M. S.:
  Beschreibung von regulären und rationalen Relationen mittels erststufiger Prädikatenlogik.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Till Tantau, Özgür L. Özcep.
• F.-C. S.:
  Datenbankanonymisierung auf Basis von k-means-Algorithmen.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Rüdiger Reischuk, Esfandiar Mohammadi.
• S. T.:
  Experimental analysis of algorithm substitution attacks.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Maciej Liskiewicz, Thomas Eisenbarth.
• V. W.:
  Implementierung und Benchmarking eines exakten kombinatorischen Algorithmus für eine minimale Graph Bisektion.
  Universität zu Lübeck, Institut für Theoretische Informatik, 2019.
  Gutachter: Maciej Liskiewicz, Ralf Möller.