2022

• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Algorithmica, 84:3459–3488, 2022.
  Go to website | Show abstract
  
  Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k d (which is a polynomial as d is a constant), and they do so in time m · 2d poly(d) for a small polynomial poly(d) (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k d kernel. This paper presents a deterministic solution with worst-case time 3d poly(d) for updating the kernel upon inserts and time 5d poly(d) for updates upon deletions. These bounds nearly match the time 2d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deter- ministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c k ) where c = d ? 1 + O(1/d) equals the best base known for the static setting.
• Max Bannach, Malte Skambath, Till Tantau:
  On the Parallel Parameterized Complexity of MaxSAT Variants.
  In Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022), LIPIcs, 2022.
  Go to website

2021

• Max Bannach, Zacharias Heinrich, Till Tantau, Rüdiger Reischuk:
  Dynamic Kernels for Hitting Sets and Set Packing.
  In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Volume 214 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  Go to website | Show abstract
  
  Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k^d (which is a polynomial kernel size as d is a constant), and they do so in time m? 2^d poly(d) for a small polynomial poly(d) (which is a linear runtime as d is again a constant). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k^d hitting set kernel in memory (including moments when no size-k hitting set exists). This paper presents a deterministic solution with worst-case time 3^d poly(d) for updating the kernel upon hyperedge inserts and time 5^d poly(d) for updates upon deletions. These bounds nearly match the time 2^d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a dynamic hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c^k) where c = d - 1 + O(1/d) equals the best base known for the static setting.
• Max Bannach, Till Tantau:
  On the Descriptive Complexity of Color Coding.
  MDPI Algorithms, 2021. Special Issue: Parameterized Complexity and Algorithms for Nonclassical Logics
  Go to website | Show abstract
  
  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.

2020

• Max Bannach, Till Tantau:
  Computing Hitting Set Kernels By AC^0-Circuits.
  Theory of Computing Systems, 64(3):374--399, 2020.
  Go to website | Show abstract
  
  Given a hypergraph $H = (V,E)$, what is the smallest subset $X \subseteq V$ such that $e \cap X \neq \emptyset$ holds for all $e \in E$? This problem, known as the \emph{hitting set problem,} is a basic problem in parameterized complexity theory. There are well-known kernelization algorithms for it, which get a hypergraph~$H$ and a number~$k$ as input and output a hypergraph~$H'$ such that (1) $H$ has a hitting set of size~$k$ if, and only if, $H'$ has such a hitting set and (2) the size of $H'$ depends only on $k$ and on the maximum cardinality $d$ of edges in~$H$. The algorithms run in polynomial time and can be parallelized to a certain degree: one can compute hitting set kernels in parallel time $O(d)$ -- but it was conjectured that this is the best parallel algorithm possible. We refute this conjecture and show how hitting set kernels can be computed in \emph{constant} parallel time. For our proof, we introduce a new, generalized notion of hypergraph sunflowers and show how iterated applications of the color coding technique can sometimes be collapsed into a single application.
• Max Bannach, Malte Skambath, Till Tantau:
  Kernelizing the Hitting Set Problem in Linear Sequential and Constant Parallel Time.
  In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), LIPIcs, 2020.
  Go to website | Show abstract
  
  We analyze a reduction rule for computing kernels for the hitting set problem: In a hypergraph, the link of a set c of vertices consists of all edges that are supersets of c. We call such a set critical if its link has certain easy-to-check size properties. The rule states that the link of a critical c can be replaced by c. It is known that a simple linear-time algorithm for computing hitting set kernels (number of edges) at most k^d (k is the hitting set size, d is the maximum edge size) can be derived from this rule. We parallelize this algorithm and obtain the first AC^0 kernel algorithm that outputs polynomial-size kernels. Previously, such algorithms were not even known for artificial problems. An interesting application of our methods lies in traditional, non-parameterized approximation theory: Our results imply that uniform AC^0-circuits can compute a hitting set whose size is polynomial in the size of an optimal hitting set.

2019

• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Technical report , Electronic Colloquium on Computational Complexity, 2019.
  Go to website | Show abstract
  
  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$.
• Max Bannach, Till Tantau:
  On the Descriptive Complexity of Color Coding.
  In Proceedings of STACS 2019, LIPIcs, LIPIcs, 2019.
  Go to website | Show PDF | Show abstract
  
  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, 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.
  Go to website | Show PDF | Show abstract
  
  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.

2018

• Max Bannach, Till Tantau:
  Computing Hitting Set Kernels By AC^0-Circuits.
  In Proceedings of the 35th International Symposium on Theoretical Aspects of Computer Science, LIPIcs, 2018.
  Go to website | Show PDF | Show abstract
  
  Given a hypergraph $H = (V,E)$, what is the smallest subset $X \subseteq V$ such that $e \cap X \neq \emptyset$ holds for all $e \in E$? This problem, known as the \emph{hitting set problem,} is a basic problem in parameterized complexity theory. There are well-known kernelization algorithms for it, which get a hypergraph~$H$ and a number~$k$ as input and output a hypergraph~$H'$ such that (1) $H$ has a hitting set of size~$k$ if, and only if, $H'$ has such a hitting set and (2) the size of $H'$ depends only on $k$ and on the maximum cardinality $d$ of edges in~$H$. The algorithms run in polynomial time, but are highly sequential. Recently, it has been shown that one of them can be parallelized to a certain degree: one can compute hitting set kernels in parallel time $O(d)$ -- but it was conjectured that this is the best parallel algorithm possible. We refute this conjecture and show how hitting set kernels can be computed in \emph{constant} parallel time. For our proof, we introduce a new, generalized notion of hypergraph sunflowers and show how iterated applications of the color coding technique can sometimes be collapsed into a single application.
• Max Bannach, Till Tantau:
  Computing Kernels in Parallel: Lower and Upper Bounds.
  In Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), LIPIcs, 2018.
  Go to website | Show PDF | Show abstract
  
  Parallel fixed-parameter tractability studies how parameterized problems can be solved in parallel. A surprisingly large number of parameterized problems admit a high level of parallelization, but this does not mean that we can also efficiently compute small problem kernels in parallel: known kernelization algorithms are typically highly sequential. In the present paper, we establish a number of upper and lower bounds concerning the sizes of kernels that can be computed in parallel. An intriguing finding is that there are complex trade-offs between kernel size and the depth of the circuits needed to compute them: For the vertex cover problem, an exponential kernel can be computed by AC$^0$-circuits, a quadratic kernel by TC$^0$-circuits, and a linear kernel by randomized NC-circuits with derandomization being possible only if it is also possible for the matching problem. Other natural problems for which similar (but quantitatively different) effects can be observed include tree decomposition problems parameterized by the vertex cover number, the undirected feedback vertex set problem, the matching problem, or the point line cover problem. We also present natural problems for which computing kernels is inherently sequential.

2017

• Till Tantau:
  Applications of Algorithmic Metatheorems to Space Complexity and Parallelism (Invited Talk)..
  In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), pp. 4:1--4:4. DROPS, 2017.
  Go to website | Show abstract
  
  Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs are structured in a certain way, then the problem can be solved with a certain amount of resources. As an example, by Courcelle's Theorem all monadic second-order ("in a certain logic") properties of graphs of bounded tree width ("structured in a certain way") can be solved in linear time ("with a certain amount of resources"). Such theorems have become a valuable tool in algorithmics: If a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. The talk is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space classes and parallel computation, and tries to give a flavor of the range of

2016

• Max Bannach, Till Tantau:
  Parallel Multivariate Meta-Theorems.
  In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), LIPIcs, 2016.
  Go to website | Show PDF | Show abstract
  
  Fixed-parameter tractability is based on the observation that many hard problems become tractable even on large inputs as long as certain input parameters are small. Originally, ``tractable'' just meant ``solvable in polynomial time,'' but especially modern hardware raises the question of whether we can also achieve ``solvable in polylogarithmic parallel time.'' A framework for this study of \emph{parallel fixed-parameter tractability} is available and a number of isolated algorithmic results have been obtained in recent years, but one of the unifying core tools of classical FPT theory has been missing: algorithmic meta-theorems. We establish two such theorems by giving new upper bounds on the circuit depth necessary to solve the model checking problem for monadic second-order logic, once parameterized by the tree width and the formula (this is a parallel version of Courcelle's Theorem) and once by the tree depth and the formula. For our proofs we refine the analysis of earlier algorithms, especially of Bodlaender's, but also need to add new ideas, especially in the context where the parallel runtime is bounded by a function of the parameter and does not depend on the length of the input.
• Michael Elberfeld, Martin Grohe, Till Tantau:
  Where First-Order and Monadic Second-Order Logic Coincide.
  Transactions on Computational Logic, (Volume 17 Issue 4, November 2016 Article No. 25)2016.
• Malte Skambath, Till Tantau:
  Offline Drawing of Dynamic Trees: Algorithmics and Document Integration.
  In GD 2016: Graph Drawing and Network Visualization, Volume 9801 of LNCS, pp. 572-586. Springer, 2016.
  Go to website | Show abstract
  
  While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular Open image in new window typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running Open image in new window on the documents then results in documents in the svg format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.
• Malte Skambath, Till Tantau:
  Offline Drawing of Dynamic Trees: Algorithmics and Document Integration Analysis of Binary Search Trees.
  Technical report arXiv:1608.08385, CoRR, 2016.
  Go to website | Show abstract
  
  While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular TEX typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running TEX on the documents then results in documents in the SVG format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.
• Till Tantau:
  A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes.
  Algorithms, 9(3):1-44, 2016.
  Go to website | Show abstract
  
  Algorithmic metatheorems state that if a problem can be described in a certain logic and the inputs are structured in a certain way, then the problem can be solved with a certain amount of resources. As an example, by Courcelle’s Theorem, all monadic second-order (“in a certain logic”) properties of graphs of bounded tree width (“structured in a certain way”) can be solved in linear time (“with a certain amount of resources”). Such theorems have become valuable tools in algorithmics: if a problem happens to have the right structure and can be described in the right logic, they immediately yield a (typically tight) upper bound on the time complexity of the problem. Perhaps even more importantly, several complex algorithms rely on algorithmic metatheorems internally to solve subproblems, which considerably broadens the range of applications of these theorems. This paper is intended as a gentle introduction to the ideas behind algorithmic metatheorems, especially behind some recent results concerning space and circuit classes, and tries to give a flavor of the range of their applications.

2015

• Max Bannach, Christoph Stockhusen, Till Tantau:
  Fast Parallel Fixed-Parameter Algorithms via Color Coding.
  In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), LIPIcs, 2015.
  Go to website | Show PDF | Show abstract
  
  Fixed-parameter algorithms have been successfully applied to solve numerous difficult problems within acceptable time bounds on large inputs. However, most fixed-parameter algorithms are inherently \emph{sequential} and, thus, make no use of the parallel hardware present in modern computers. We show that parallel fixed-parameter algorithms do not only exist for numerous parameterized problems from the literature -- including vertex cover, packing problems, cluster editing, cutting vertices, finding embeddings, or finding matchings -- but that there are parallel algorithms working in \emph{constant} time or at least in time \emph{depending only on the parameter} (and not on the size of the input) for these problems. Phrased in terms of complexity classes, we place numerous natural parameterized problems in parameterized versions of AC$^0$. On a more technical level, we show how the \emph{color coding} method can be implemented in constant time and apply it to embedding problems for graphs of bounded tree-width or tree-depth and to model checking first-order formulas in graphs of bounded degree.
• Michael Elberfeld, Christoph Stockhusen, Till Tantau:
  On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness.
  Algorithmica, 71(3):661-701, 2015.
  Go to website | Show abstract
  
  The parameterized complexity of a problem is generally considered ``settled'' once it has been shown to be fixed-parameter tractable or to be complete for a class in a parameterized hierarchy such as the weft hierarchy. Several natural parameterized problems have, however, resisted such a classification. In the present paper we argue that, %at least in some cases, this is due to the fact that the parameterized complexity of these problems can be better understood in terms of their \emph{parameterized space} or \emph{parameterized circuit} complexity. This includes well-studied, natural problems like the feedback vertex set problem, the associative generability problem, or the longest common subsequence problem. We show that these problems lie in and may even be complete for different parameterized space classes, leading to new insights into the problems' complexity. The classes we study are defined in terms of different forms of bounded nondeterminism and simultaneous time--space bounds.
• Till Tantau:
  Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification.
  In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Volume 30 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 703-715. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015.
  Go to website | Show abstract
  
  Descriptive complexity theory aims at inferring a problem's computational complexity from the syntactic complexity of its description. A cornerstone of this theory is Fagin's Theorem, by which a property is expressible in existential second-order logic (ESO logic) if, and only if, it is in NP. A natural question, from the theory's point of view, is which syntactic fragments of ESO logic also still characterize NP. Research on this question has culminated in a dichotomy result by Gottlob, Kolaitis, and Schwentick: for each possible quantifier prefix of an ESO formula, the resulting prefix class over graphs either contains an NP-complete problem or is contained in P. However, the exact complexity of the prefix classes inside P remained elusive. In the present paper, we clear up the picture by showing that for each prefix class of ESO logic, its reduction closure under first-order reductions is either FO, L, NL, or NP. For undirected self-loop-free graphs two containment results are especially challenging to prove: containment in L for the prefix \exists R_1\cdots \exists R_n \forall x \exists y and containment in FO for the prefix \exists M \forall x \exists y for monadic M. The complex argument by Gottlob et al. concerning polynomial time needs to be carefully reexamined and either combined with the logspace version of Courcelle's Theorem or directly improved to first-order computations. A different challenge is posed by formulas with the prefix \exists M \forall x\forall y, which we show to express special constraint satisfaction problems that lie in L.

2013

• Christoph Stockhusen, Till Tantau:
  Completeness Results for Parameterized Space Classes.
  Technical report arxiv:1308.2892, ArXiv, 2013.
  Go to website | Show abstract
  
  The parameterized complexity of a problem is considered "settled" once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a "union operation" that translates between problems complete for classical complexity classes and for W-classes.
• Christoph Stockhusen, Till Tantau:
  Completeness Results for Parameterized Space Classes.
  In 8th International Symposium on Parameterized and Exact Computation (IPEC 2013), Lecture Notes in Computer Science, Springer, 2013 (to appear).
  Show abstract
  
  The parameterized complexity of a problem is generally considered ``settled'' once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized \emph{space} complexity have recently been obtained that rule out completeness results for parameterized \emph{time} classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a ``union operation'' that translates between problems complete for classical complexity classes and for W-classes.
• Till Tantau:
  Graph Drawing in TikZ.
  In Proceedings of Graph Drawing 2012, Volume 7704 of Lecture Notes in Computer Science, pp. 517-528. Springer, 2013.
  Show abstract
  
  At the heart of every good graph drawing algorithm lies an efficient procedure for assigning canvas positions to a graph's nodes and the bend points of its edges. However, every real-world implementation of such an algorithm must address numerous problems that have little to do with the actual algorithm, like handling input and output for-mats, formatting node texts, and styling nodes and edges. We present a new framework, implemented in the Lua programming language and integrated into the TikZ graphics description language, that aims at sim-plifying the implementation of graph drawing algorithms. Implementers using the framework can focus on the core algorithmic ideas and will au-tomatically profit from the framework's pre- and post-processing steps as well as from the extensive capabilities of the TikZ graphics language and the TeX typesetting engine. Algorithms already implemented using the framework include the Reingold-Tilford tree drawing algorithm, a mod-ular version of Sugiyama's layered algorithm, and several force-based multilevel algorithms.
• Till Tantau:
  Graph Drawing in TikZ.
  Journal of Graph Algorithms and Applications, 17(4):495-513, 2013.
  Show PDF | Show abstract
  
  At the heart of every good graph drawing algorithm lies an efficient procedure for assigning canvas positions to a graph's nodes and the bend points of its edges. However, every real-world implementation of such an algorithm must address numerous problems that have little to do with the actual algorithm, like handling input and output for-mats, formatting node texts, and styling nodes and edges. We present a new framework, implemented in the Lua programming language and integrated into the TikZ graphics description language, that aims at sim-plifying the implementation of graph drawing algorithms. Implementers using the framework can focus on the core algorithmic ideas and will au-tomatically profit from the framework's pre- and post-processing steps as well as from the extensive capabilities of the TikZ graphics language and the TeX typesetting engine. Algorithms already implemented using the framework include the Reingold-Tilford tree drawing algorithm, a mod-ular version of Sugiyama's layered algorithm, and several force-based multilevel algorithms.

2012

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

2011

• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth.
  Technical report ECCC-TR11-128, Electronic Colloquium on Computational Complexity, 2011.
  Show PDF | Go to website | Show abstract
  
  An algorithmic meta theorem for a logic and a class C of structures states that all problems expressible 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 solvable 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 problems 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 decompositions of trees in TC0, which encapsulates most of the technical difficulties surrounding earlier results connecting tree automata and NC1.

2010

• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Logspace Versions of the Theorems of Bodlaender and Courcelle.
  In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010), pp. 143-152. IEEE Computer Society, 2010.
  Go to website | Show abstract
  
  Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.
• Michael Elberfeld, Andreas Jakoby, Till Tantau:
  Logspace Versions of the Theorems of Bodlaender and Courcelle.
  Technical report ECCC-TR10-062, Electronic Colloquium on Computational Complexity, 2010.
  Show PDF | Go to website | Show abstract
  
  Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.
• Michael Elberfeld, Till Tantau:
  Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  Technical report SIIM-TR-A-10-01, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2010.
  Show PDF | 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 evolution- ary model where a perfect phylogenetic tree is sought that explains the observed data. In their CPM’09 paper, Fellows et al. studied an exten- sion of this approach that incorporates prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. While this approach is attractive to increase the accuracy of haplotyping methods, it was conjectured that the resulting formal prob- lem 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.
• Michael Elberfeld, Till Tantau:
  Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  In Proceedings of the 21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), Volume 6129 of Lecture Notes in Computer Science, pp. 177-189. Springer, 2010.
  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. In their CPM 2009 paper, Fellows et al. studied an extension of this approach that incorporates prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. While this approach may help to increase the accuracy of haplotyping methods, it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the present paper 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.
• Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
  On the Complexity of Kings.
  Theoretical Computer Science, 411(2010):783-798, 2010.
  Go to website | Show abstract
  
  A k-king in a directed graph is a node from which each node in the graph can be reached via paths of length at most~k. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems and semifeasible sets. In this paper, we study the complexity of recognizing k-kings. For each succinctly specified family of tournaments (completely oriented digraphs), the k-king problem is easily seen to belong to $\Pi_2^{\mathrm p}$. We prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in $\Pi_2^{\mathrm p}$. That is, we show that for every $k \ge 2$ every set in $\Pi_2^{\mathrm p}$ other than $\emptyset$ and $\Sigma^*$ is equivalent to a k-king problem under $\leq_{\mathrm m}^{\mathrm p}$-reductions. The equivalence can be instantiated via a simple padding function. Our results can be used to show that the radius problem for arbitrary succinctly represented graphs is $\Sigma_3^{\mathrm p}$-complete. In contrast, the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is $\Pi_2^{\mathrm p}$-complete.

2009

• Michael Elberfeld, Ilka Schnoor, Till Tantau:
  Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
  In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation (TAMC 2009), Volume 5532 of Lecture Notes in Computer Science, pp. 201-210. Springer, 2009.
  Show PDF | Go to website | Show abstract
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes from 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 as is often the case in laboratory data, the resulting incomplete perfect phylogeny haplotyping problem IPPH is NP-complete and no theoretical results are known concerning its approximability, fixed-parameter tractability, or exact algorithms for it. 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 a fixed-parameter algorithm is known. We show that such drastic and ad hoc simplifications are not necessary to make IPPH fixed-parameter tractable: We present the first theoretical analysis of an algorithm, which we develop in the course of the paper, that works for arbitrary instances of IPPH. On the negative side we show that restricting the topology of perfect phylogenies does not always reduce the computational complexity: while the incomplete directed perfect phylogeny problem is well-known to be solvable in polynomial time, we show that the same problem restricted to path topologies is NP-complete.
• Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
  On the complexity of SNP block partitioning under the perfect phylogeny model.
  Discrete Mathematics, 309(18):5610-5617, 2009.
  Go to website | Show abstract
  
  ecent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genome-wide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for large-scale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkage-disequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of non-contiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is NP-hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.

2008

• Jens Gramm, Arfst Nickelsen, Till Tantau:
  Fixed-Parameter Algorithms in Phylogenetics.
  In Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, Volume 452 of Methods in Molecular Biology, pp. 507-535. Springer, 2008.
  Show abstract
  
  We survey the use of fixed-parameter algorithms in phylogenetics. A central computational problem in this field is the construction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype, on differences in the genotype, or on given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from an elementary evolutionary model, but in practice one must often be content with phylogenies whose "distance from perfection" is as small as possible. The computation of phylogenies also has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics are often NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.
• Bodo Manthey, Till Tantau:
  Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
  In Proceedings of MFCS 2008, Volume 5162 of Lecture Notes in Computer Science, pp. 467-478. Springer, 2008.
  Show abstract
  
  Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. We analyze their smoothed height under additive uniform noise: An adversary chooses a sequence of~$n$ real numbers in the range $[0,1]$, each number is individually perturbed by adding a value drawn uniformly at random from an interval of size~$d$, and the resulting numbers are inserted into a search tree. An analysis of the smoothed tree height subject to $n$ and $d$ lies at the heart of our paper: We prove that the smoothed height of binary search trees is $\Theta (\sqrt{n/d} + \log n)$, where $d \ge 1/n$ may depend on~$n$. Our analysis starts with the simpler problem of determining the smoothed number of left-to-right maxima in a sequence. We establish matching bounds, namely once more $\Theta (\sqrt{n/d} + \log n)$. We also apply our findings to the performance of the quicksort algorithm and prove that the smoothed number of comparisons made by quicksort is $\Theta(\frac{n}{d+1} \sqrt{n/d} + n \log n)$.
• Till Tantau:
  Complexity of the Undirected Radius and Diameter Problems for Succinctly Represented Graphs.
  Technical report SIIM-TR-A-08-03, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
  Show PDF
• Till Tantau:
  Der One-Time-Pad-Algorithmus.
  In Taschenbuch der Algorithmen, Springer, 2008.
  Show abstract
  
  Ein Beitrag über den One-Time-Pad-Algorithmus im Rahmen der Algorithmen der Woche während des Jahrs der Informatik 2006.
• Till Tantau:
  Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets.
  Technical report ECCC-TR08-027, Electronic Colloquium on Computational Complexity, 2008.
  Show PDF | Show abstract
  
  The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets: 1. E = UE if, and only if, all functions f: {1}^* to Sigma^* in NPSV_g lie in FP. 2. E = NE if, and only if, all functions f: {1}^* to Sigma^* in NPFewV lie in FP. 3. E = E^NP if, and only if, all functions f: {1}^* to Sigma^* in OptP lie in FP. 4. E = E^NP if, and only if, all standard left cuts in NP lie in P. 5. E = EH if, and only if, PH cap P/poly = P. We apply these results to the immunity of P-selective sets. It is known that they can be bi-immune, but not Pi_2^p/1-immune. Their immunity is closely related to top-Toda languages, whose complexity we link to the exponential realm, and also to king languages. We introduce the new notion of superkings, which are characterized in terms of existsforall-predicates rather than forallexists-predicates, and show that king languages cannot be Sigma_2^p-immune. As a consequence, P-selective sets cannot be Sigma_2^/1-immune and, if E^NP^NP = E, not even P/1-immune.
• Michael Elberfeld, Till Tantau:
  Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
  Technical report SIIM-TR-A-08-02, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
  Show PDF | Show abstract
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. This problem, which has strong practical applications, can be approached using both statistical as well as combinatorial methods. While the most direct combinatorial approach, maximum parsimony, leads to NP-complete problems, the perfect phylogeny model proposed by Gusfield yields a problem, called PPH, that can be solved in polynomial (even linear) time. Even this may not be fast enough when the whole genome is studied, leading to the question of whether parallel algorithms can be used to solve the PPH problem. In the present paper we answer this question affirmatively, but we also give lower complexity bounds on its complexity. In detail, we show that the problem lies in Mod$_2$L, a subclass of the circuit complexity class NC$^2$, and is hard for logarithmic space and thus presumably not in NC$^1$. We also investigate variants of the PPH problem that have been studied in the literature, like the perfect path phylogeny haplotyping problem and the combined problem where a perfect phylogeny of maximal parsimony is sought, and show that some of these variants are TC$^0$-complete or lie in AC$^0$.
• Michael Elberfeld, Till Tantau:
  Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.
  In Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Volume 5162 of Lecture Notes in Computer Science, pp. 299-310. Springer, 2008.
  Go to website | Show abstract
  
  Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. This problem, which has strong practical applications, can be approached using both statistical as well as combinatorial methods. While the most direct combinatorial approach, maximum parsimony, leads to NP-complete problems, the perfect phylogeny model proposed by Gusfield yields a problem, called PPH, that can be solved in polynomial (even linear) time. Even this may not be fast enough when the whole genome is studied, leading to the question of whether parallel algorithms can be used to solve the PPH problem. In the present paper we answer this question affirmatively, but we also give lower complexity bounds on its complexity. In detail, we show that the problem lies in Mod$_2$L, a subclass of the circuit complexity class NC$^2$, and is hard for logarithmic space and thus presumably not in NC$^1$. We also investigate variants of the PPH problem that have been studied in the literature, like the perfect path phylogeny haplotyping problem and the combined problem where a perfect phylogeny of maximal parsimony is sought, and show that some of these variants are TC$^0$-complete or lie in AC$^0$.
• Michael Elberfeld, Ilka Schnoor, Till Tantau:
  Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
  Technical report SIIM-TR-A-08-05, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2008.
  Show PDF | 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, as is often the case in real laboratory data, the resulting formal problem IPPH, which stands for incomplete perfect phylogeny haplotyping, is NP-complete and no theoretical results are known concerning its approximability, fixed-parameter tractability or exact algorithms for it. 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. We generalize this algorithm to arbitrary tree topologies and present the first theoretical analysis of an algorithm that works on arbitrary instances of the original IPPH problem. At the same time we also show that restricting the tree topology does not always make finding phylogenies easier: while the incomplete directed perfect phylogeny problem is well-known to be solvable in polynomial time, we show that the same problem restricted to path topologies is NP-complete.
• Jens Gramm, Arfst Nickelsen, Till Tantau:
  Fixed-Parameter Algorithms in Phylogenetics.
  The Computer Journal, 51(1):79--101, 2008.
  Show PDF | Show abstract
  
  We survey the use of fixed-parameter algorithms in the field of phylogenetics, which is the study of evolutionary relationships. The central problem in phylogenetics is the reconstruction of the evolutionary history of biological species, but its methods also apply to linguistics, philology, or architecture. A basic computational problem is the reconstruction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype like color or form of limbs, based on differences in the genotype like mutated nucleotide positions in the DNA sequence, or based on given partial phylogenies. Ideally, one would like to construct so-called perfect phylogenies, which arise from a very simple evolutionary model, but in practice one must often be content with phylogenies whose ``distance from perfection'' is as small as possible. The computation of phylogenies has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics often are NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.

2007

• Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
  Haplotyping with Missing Data via Perfect Path Phylogenies.
  Discrete and Applied Mathematics, 155:788-805, 2007.
  Show abstract
  
  Computational methods for inferring haplotype information from genotype data are used in studying the association between genomic variation and medical condition. Recently, Gusfield proposed a haplotype inference method that is based on perfect phylogeny principles. A fundamental problem arises when one tries to apply this approach in the presence of missing genotype data, which is common in practice. We show that the resulting theoretical problem is NP-hard even in very restricted cases. To cope with missing data, we introduce a variant of haplotyping via perfect phylogeny in which a path phylogeny is sought. Searching for perfect path phylogenies is strongly motivated by the characteristics of human genotype data: 70% of real instances that admit a perfect phylogeny also admit a perfect path phylogeny. Our main result is a fixed-parameter algorithm for haplotyping with missing data via perfect path phylogenies. We also present a simple linear-time algorithm for the problem on complete data.
• Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
  On the Complexity of Kings.
  In Proceedings of FCT 2007, Volume 4639 of Lecture Notes in Computer Science, pp. 328--340. Springer, 2007.
  Show abstract
  
  A k-king in a directed graph is a node from which each node in the graph can be reached via paths of length at most~k. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems and semifeasible sets. In this paper, we study the complexity of recognizing k-kings. For each succinctly specified family of tournaments (completely oriented digraphs), the k-king problem is easily seen to belong to $\Pi_2^{\mathrm p}$. We prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in $\Pi_2^{\mathrm p}$. That is, we show that for every $k \ge 2$ every set in $\Pi_2^{\mathrm p}$ other than $\emptyset$ and $\Sigma^*$ is equivalent to a k-king problem under $\leq_{\mathrm m}^{\mathrm p}$-reductions. The equivalence can be instantiated via a simple padding function. Our results can be used to show that the radius problem for arbitrary succinctly represented graphs is $\Sigma_3^{\mathrm p}$-complete. In contrast, the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is $\Pi_2^{\mathrm p}$-complete.
• Andreas Jakoby, Till Tantau:
  Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.
  In Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), Volume 4855 of Lecture Notes in Computer Science, pp. 216-227. Springer, 2007.
  Show abstract
  
  For many types of graphs, including directed acyclic graphs, undirected graphs, tournament graphs, and graphs with bounded independence number, the shortest path problem is NL-complete. The longest path problem is even NP-complete for many types of graphs, including undirected K₅-minor-free graphs and even planar graphs. In the present paper we present logspace algorithms for computing shortest and longest paths in series-parallel graphs where the edges can be directed arbitrarily. The class of series-parallel graphs that we study can be characterized alternatively as the class of K₄-minor-free graphs and also as the class of graphs of tree-width 2. It is well-known that for graphs of bounded tree-width many intractable problems can be solved efficiently, but previous work was focused on finding algorithms with low parallel or sequential time complexity. In contrast, our results concern the space complexity of shortest and longest path problems. In particular, our results imply that for graphs of tree-width 2 these problems are L-complete.
• Bodo Manthey, Till Tantau:
  Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise.
  Technical report ECCC-TR07-039, Electronic Colloquium on Computational Complexity, 2007.
  Go to website | Show abstract
  
  Binary search trees are a fundamental data structure and their height plays a key role in the analysis of divide-and-conquer algorithms like quicksort. Their worst-case height is linear; their average height, whose exact value is one of the best-studied problems in average-case complexity, is logarithmic. We analyze their smoothed height under additive noise: An adversary chooses a sequence of n real numbers in the range [0,1]; each number is individually perturbed by adding a random value from an interval of size d; and the resulting numbers are inserted into a search tree. The expected height of this tree is called smoothed tree height. If d is very small, namely for d < 1/n, the smoothed tree height is the same as the worst-case height; if d is very large, the smoothed tree height approaches the logarithmic average-case height. An analysis of what happens between these extremes lies at the heart of our paper: We prove that the smoothed height of binary search trees is $Theta (sqrt{n/d} + log n)$, where d >= 1/n may depend on n. This implies that the logarithmic average-case height becomes manifest only for $d in Omega (n/log^2 n)$. For the analysis, we first prove that the smoothed number of left-to-right maxima in a sequence is also $Theta (sqrt{n/d} + log n)$. We apply these findings to the performance of the quicksort algorithm, which needs $Theta(n^2)$ comparisons in the worst case and $Theta(n log n)$ on average, and prove that the smoothed number of comparisons made by quicksort is $Theta(n/d+1 sqrt{n/d} + n log n)$. This implies that the average-case becomes manifest already for $d in Omega(sqrt[3]{n/logsqr n})$.
• Till Tantau:
  Logspace Optimization Problems and Their Approximability Properties.
  Theory of Computing Systems, 41(2):327-350, 2007.
  Show abstract
  
  Logspace optimization problems are the logspace analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties, even though the underlying decision problems have the same computational complexity. Natural problems -- including the shortest path problems for directed graphs, undirected graphs, tournaments, and forests -- exhibit such a varying complexity. In order to study the approximability of logspace optimization problems in a systematic way, polynomial-time approximation classes and polynomial-time reductions between optimization problems are transferred to logarithmic space. It is proved that natural problems are complete for different logspace approximation classes. This is used to show that under the assumption L \neq NL some logspace optimization problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but cannot be solved in logarithmic space.

2006

• Jens Gramm, Tzvika Hartman, Till Nierhoff, Roded Sharan, Till Tantau:
  On the Complexity of SNP Block Partitioning Under the Perfect Phylogeny Model.
  In Proceedings of Workshop on Algorithms in Bioinformatics (WABI), Volume 4175 of Lecture Notes in Computer Science, pp. 92-102. Springer, 2006.
  Show abstract
  
  Recent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genome-wide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for large-scale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkage-disequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of non-contiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is NP-hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.
• Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
  On the Complexity of Kings.
  Technical report URCS-TR905, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2006.
  Go to website | Show abstract
  
  A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king [Lan53]. Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems [Tan01,NT05]. and semifeasible sets [HNP98,HT06,HOZZ06]. In this paper, we study the complexity of recognizing kings. For each succinctly specified family of tournaments, the king problem is already known to belong to $\Pi_2^p$ [HOZZ06]. We prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in $\Pi_2^p$. That is, we show that \emph{every} set in $\Pi_2^p$ other than $\emptyset$ and $\Sigma^*$ is equivalent to a king problem under $\leq_m^p$-reductions. Indeed, we show that the equivalence can even be instantiated via relatively simple padding, and holds even if the notion of kings is redefined to refer to k-kings (for any fixed $k \geq 2$)---nodes from which the all nodes can be reached via paths of length at most k. Using these and related techniques, we obtain a broad range of additional results about the complexity of king problems, diameter problems, radius problems, and initial component problems. It follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is $\Pi_2^p$-complete. We show that the radius problem for arbitrary succinctly represented graphs is $\Sigma_3^p$-complete, but that in contrast the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is $\Pi_2^p$-complete. Yet again in contrast, we prove that initial component languages (which ask whether a given node can reach all other nodes in its tournament) all fall within $\Pi_2^p$, yet cannot be $\Pi_2^p$-complete---or even NP-hard---unless P=NP.
• Richard Karp, Till Nierhoff, Till Tantau:
  Optimal Flow Distribution Among Multiple Channels with Unknown Capacities.
  In Essays in Theoretical Computer Science in Memory of Shimon Even, Volume 3895 of Lecture Notes in Computer Science - Festschriften, pp. 111-128. Springer, 2006.
  Show abstract
  
  Consider a simple network flow problem in which a flow of value D must be split among n channels directed from a source to a sink. The initially unknown channel capacities can be probed by attempting to send a flow of at most D units through the network. If the flow is not feasible, we are told on which channels the capacity was exceeded (binary feedback) and possibly also how many units of flow were successfully sent on these channels (throughput feedback). For throughput feedback we present optimal protocols for minimizing the number of rounds needed to find a feasible flow and for minimizing the total amount of wasted flow. For binary feedback we present an asymptotically optimal protocol.
• Till Tantau:
  The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
  Technical report ECCC-TR06-035, Electronic Colloquium on Computational Complexity, 2006.
  Go to website | Show abstract
  
  The reachability problem for graphs cannot be described, in the sense of descriptive complexity theory, using a single first-order formula. This is true both for directed and undirected graphs, both in the finite and infinite. However, if we restrict ourselves to graphs in which a certain graph parameter is fixed to a certain value, first-order formulas often suffice. A trivial example are graphs whose number of vertices is fixed to n. In such graphs reachability can be described using a first-order formula with a quantifier nesting depth of log₂ n, which is both a lower and an upper bound. In this paper we investigate how the descriptive complexity of the reachability problem varies as a function of graph parameters such as the size of the graph, the clique number, the matching number, the independence number or the domination number. The independence number turns out to be the by far most challenging graph parameter.

2005

• Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
  Contextfree Languages Can Be Accepted With Absolutely No Space Overhead.
  Information and Computation, 203(2):163-180, 2005.
  Show abstract
  
  We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.
• Richard Karp, Till Nierhoff, Till Tantau:
  Optimal Flow Distribution Among Multiple Channels with Unknown Capacities.
  In Proceedings of the 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Volume 19 of Electronic Notes in Discrete Mathematics, pp. 225-231. Springer, 2005.
  Show abstract
  
  Consider a simple network flow problem in which there are n channels directed from a source to a sink. The channel capacities are unknown and we wish to determine a feasible network flow of value D. Flow problems with unknown capacities arise naturally in numerous applications, including inter-domain traffic routing in the Internet [Chandrayana et al. 2004], bandwidth allocation for sending files in peer-to-peer networks, and the distribution of physical goods like newspapers among different points of sale. We study protocols that probe the network by attempting to send a flow of at most D units through the network. If the flow is not feasible, the protocol is told on which channels the capacity was exceeded (binary feedback) and possibly also how many units of flow were successfully send on these channels (throughput feedback). For the latter, more informative, type of feedback we present optimal protocols for minimizing the number of rounds needed to find a feasible flow and for minimizing the total amount of wasted flow. For binary feedback, we show that one can exploit the fact that network capacities are often larger than the demand D: We present a protocol for this situation that is asymptotically optimal and finds a solution more quickly than the generalized binary search protocol previously proposed in the literature [Chandrayana et al. 2004]. For the special case of two channels we present a protocol that is optimal and outperforms binary search.
• Arfst Nickelsen, Till Tantau:
  The Complexity of Finding Paths in Graphs with Bounded Independence Number.
  SIAM Journal on Computing, 34(5):1176-1195, 2005.
  Show abstract
  
  We study the problem of finding a path between two vertices in finite directed graphs whose independence number is bounded by some constant k. The independence number of a graph is the largest number of vertices that can be picked such that there is no edge between any two of them. The complexity of this problem depends on the exact question we ask: Do we only wish to tell whether a path exists? Do we also wish to construct such a path? Are we required to construct the shortest one? Concerning the first question, we show that the reachability problem is first-order definable for all k and that its succinct version is Pi₂^P-complete for all k. In contrast, the reachability problems for many other types of finite graphs, including dags and trees, are not first-order definable and their succinct versions are PSPACE-complete. Concerning the second question, we show that not only can we construct paths in logarithmic space, there even exists a logspace approximation scheme for this problem. The scheme gets a ratio r ≥ 1 as additional input and outputs a path that is at most r times as long as the shortest path. Concerning the third question, we show that even telling whether the shortest path has a certain length is NL-complete and thus as difficult as for arbitrary directed graphs.
• Till Tantau:
  Logspace Optimization Problems and Their Approximability Properties.
  In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Volume 3623 of Lecture Notes in Computer Science, pp. 92-103. Springer, 2005.
  Show abstract
  
  This paper introduces logspace optimization problems as analogues of the well-studied polynomial-time optimization problems. Similarly to them, logspace optimization problems can have vastly different approximation properties, even though the underlying decision problems have the same computational complexity. Natural problems, including the shortest path problems for directed graphs, undirected graphs, tournaments, and forests, exhibit such a varying complexity. In order to study the approximability of logspace optimization problems in a systematic way, polynomial-time approximation classes are transferred to logarithmic space. Appropriate reductions are defined and optimization problems are presented that are complete for these classes. It is shown that under the assumption L neq NL some logspace optimization problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but cannot be solved in logarithmic space. A new natural NL-complete problem is presented that has a logspace approximation scheme.
• Till Tantau:
  Weak Cardinality Theorems.
  Journal of Symbolic Logic, 70(3):861-878, 2005.
  Show abstract
  
  Kummer's Cardinality Theorem states that a language A must be recursive if a Turing machine can exclude for any n words w1, ..., wn one of the n + 1 possibilities for the cardinality of {w1, ..., wn} \cap A. There was good reason to believe that this theorem is a peculiarity of recursion theory: neither the Cardinality Theorem nor weak forms of it hold for classical resource-bounded computational models like polynomial time. This belief may be flawed. In this paper it is shown that Weak Cardinality Theorems hold for finite automata and also for other models. A mathematical explanation is given as to ``why'' recursion-theoretic and automata-theoretic Weak Cardinality Theorems hold, but not corresponding `middle-ground theorems': the recursion- and automata-theoretic Weak Cardinality Theorems are instantiations of purely logical Weak Cardinality Theorems. The logical theorems can be instantiated for logical structures characterizing recursive computations and finite automata computations. A corresponding structure characterizing polynomial time does not exist.

2004

• Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
  On the Complexity of Haplotyping via Perfect Phylogeny.
  In Proceedings of Second RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotypes, pp. 35-46. , 2004.
  Show abstract
  
  The problem of haplotyping via perfect phylogeny has received a lot of attention lately due to its applicability to real haplotyping problems and its theoretical elegance. However, two main research issues remained open: The complexity of haplotyping with missing data, and whether the problem is linear-time solvable. In this paper we settle the first question and make progress toward answering the second one. Specifically, we prove that Perfect Phylogeny Haplotyping with missing data is NP-complete even when the phylogeny is a path and only one allele of every polymorphic site is present in the population in its homozygous state. Our result implies the hardness of several variants of the missing data problem, including the general Perfect Phylogeny Haplotyping Problem with missing data, and Hypergraph Tree Realization with missing data. On the positive side, we give a linear-time algorithm for Perfect Phylogeny Haplotyping when the phylogeny is a path. This variant is important due to the abundance of yin-yang haplotypes in the human genome. Our algorithm relies on a reduction of the problem to that of deciding whether a partially ordered set has width~2.
• Jens Gramm, Till Nierhoff, Till Tantau:
  Perfect Path Phylogeny Haplotyping with Missing Data is Fixed-Parameter Tractable.
  In Proceedings of the 2004 International Workshop on Parameterized and Exact Computation, Volume 3162 of Lecture Notes in Computer Science, pp. 174-186. Springer, 2004.
  Show abstract
  
  Haplotyping via perfect phylogeny is a method for retrieving haplotypes from genotypes. Fast algorithms are known for computing perfect phylogenies from complete and error-free input instances---these instances can be organized as a genotype matrix whose rows are the genotypes and whose columns are the single nucleotide polymorphisms under consideration. Unfortunately, in the more realistic setting of missing entries in the genotype matrix, even restricted forms of the perfect phylogeny haplotyping problem become NP-hard. We show that haplotyping via perfect phylogeny with missing data becomes computationally tractable when imposing additional biologically motivated constraints. Firstly, we focus on asking for perfect phylogenies that are paths, which is motivated by the discovery that yin-yang haplotypes span large parts of the human genome. A yin-yang haplotype implies that every corresponding perfect phylogeny <i>has</i> to be a path. Secondly, we assume that the number of missing entries in every column of the input genotype matrix is bounded. We show that the perfect path phylogeny haplotyping problem is fixed-parameter tractable when we consider the maximum number of missing entries per column of the genotype matrix as parameter. The restrictions we impose are met by a majority of the problem instances encountered in publicly available human genome data.
• Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
  Overhead-Free Computation, DCFLs, and CFLs.
  Technical report URCS-TR-2004-844, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2004.
  Go to website | Show abstract
  
  We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that all context-free languages can be accepted nondeterministically in polynomial time with absolutely no space overhead, and that all deterministic context-free languages can be accepted deterministically in polynomial time with absolutely no space overhead.
• Arfst Nickelsen, Till Tantau, Lorenz Weizäcker:
  Aggregates with Component Size One Characterize Polynomial Space.
  Technical report ECCC-TR04-028, Electronic Colloquium on Computational Complexity, 2004.
  Go to website | Show abstract
  
  Aggregates are a computational model similar to circuits, but the underlying graph is not necessarily acyclic. Logspace-uniform polynomial-size aggregates decide exactly the languages in PSPACE; without uniformity condition they decide the languages in PSPACE/poly. As a measure of similarity to boolean circuits we introduce the parameter component size. We prove that already aggregates of component size 1 are powerful enough to capture polynomial space. The only type of cyclic components needed to make polynomial-size circuits as powerful as polynomial-size aggregates are binary xor-gates whose output is fed back to the gate as one of the inputs.
• Mitsunori Ogihara, Till Tantau:
  On the Reducibility of Sets Inside NP to Sets with Low Information Content.
  Journal of Computer and System Sciences, 69(4):299-324, 2004.
  Show abstract
  
  This paper studies for various natural problems in NP whether they can be reduced to sets with low information content, such as branches, P-selective sets, and membership comparable sets. The problems that are studied include the satisfiability problem, the graph automorphism problem, the undirected graph accessibility problem, the determinant function, and all logspace self-reducible languages. Some of these are complete for complexity classes within NP, but for others an exact complexity-theoretic characterization is not known. Reducibility of these problems is studied in a general framework introduced in this paper: prover-verifier protocols with low-complexity provers. It is shown that all these natural problems indeed have such protocols. This fact is used to show, for certain reduction types, that these problems are not reducible to sets with low information content unless their complexity is much less than what it is currently believed to be. The general framework is also used to obtain a new characterization of the complexity class L: L is the class of all logspace self-reducible sets in L^L-sel.
• Till Tantau:
  Comparing Verboseness for Finite Automata and Turing Machines.
  Theory of Computing Systems, 37(1):95-109, 2004.
  Show abstract
  
  A language is called (m,n)-verbose if there exists a Turing machine that enumerates for any n words at most m possibilities for their characteristic string. We compare this notion to (m,n)-fa-verboseness, where instead of a Turing machine a finite automaton is used. Using a new structural diagonalisation method, where finite automata trick Turing machines, we prove that all (m,n)-verbose languages are (h,k)-verbose, iff all (m,n)-fa-verbose languages are (h,k)-fa-verbose. In other words, Turing machines and finite automata behave in exactly the same way with respect to inclusion of verboseness classes. This identical behaviour implies that the Nonspeedup Theorem also holds for finite automata. As an application of the theoretical framework, we prove a lower bound on the number of bits needed to be communicated to finite automata protocol checkers for nonregular protocols.
• Till Tantau:
  Strahlende Präsentationen in LaTeX.
  Die TeXnische Komödie, 2/04:54-80, 2004. In German.
  Go to website | Show abstract
  
  Die LaTeX-Klasse beamer dient dem Erstellen von Prsentationen mittels LaTeX, pdfLaTeX oder LyX. Wie der Name der Klasse schon verrät, will beamer es insbesondere leicht machen, Beamervorträge zu erzeugen; klassische Folienvorträge werden aber genauso unterstützt. Soweit möglich baut beamer auf dem Benutzer vertrauten LaTeX-Befehlen auf, wie \section zur Erzeugung von Abschnitten oder enumerate zur Erzeugung von Aufzählungen. Beamervorträge profitieren oft von der Verwendung von Overlays und deren Erstellung wird durch eine einfache, aber mächtige Syntaxerweiterung erleichtert. Die Klasse folgt der LaTeX-Philosophie der Trennung von Form und Inhalt: Aus einer einzigen Quelle lassen sich durch Variation von Layout-Parametern verschieden gestaltete Vorträge erzeugen. Vorgefertigte Layouts reichen von klassisch-sachlich bis modisch-effektvoll, folgen aber immer dem Bauhausgrundsatz "form follows function".
• Till Tantau:
  Über strukturelle Gemeinsamkeiten der Aufzählbarkeitsklassen von Turingmaschinen und endlichen Automaten.
  In Ausgezeichnete Informatikdissertationen 2003, Lecture Notes in Informatics, pp. 189-198. Springer, 2004.
  Show abstract
  
  Der Beitrag enthält eine Zusammenfassung der Dissertation On Structural Similarities of Finite Automata and Turing Machine Enumerability Classes.
• Till Tantau:
  A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number.
  In Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), Volume 2996 of Lecture Notes in Computer Science, pp. 326-337. Springer, 2004.
  Show PDF | Show abstract
  
  How difficult is it to find a path between two vertices in finite directed graphs whose independence number is bounded by some constant k? The independence number of a graph is the largest number of vertices that can be picked such that there is no edge between any two of them. The complexity of this problem depends on the exact question we ask: Do we only wish to tell whether a path exists? Do we also wish to construct such a path? Are we required to construct the shortest path? Concerning the first question, it is known that the reachability problem is first-order definable for all k. In contrast, the corresponding reachability problems for many other types of finite graphs, including dags and trees, are not first-order definable. Concerning the second question, in this paper it is shown that we cannot only construct paths in logarithmic space, but that there even exists a logspace approximation scheme for constructing them. In contrast, for directed graphs, undirected graphs, and dags we cannot construct paths in logarithmic space (let alone approximate the shortest one), unless complexity class collapses occur. Concerning the third question, it is shown that even telling whether the shortest path has a certain length is NL-complete and thus as difficult as for arbitrary directed graphs.

2003

• Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
  Computation with Absolutely No Space Overhead.
  In Proceedings of the Seventh International Conference on Developments in Language Theory (DLT 2003), Volume 2710 of Lecture Notes in Computer Science, pp. 325-336. Springer, 2003.
  Go to website | Show abstract
  
  We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that subclasses of the context-free languages can even be accepted in polynomial time with absolutely no space overhead.
• Arfst Nickelsen, Till Tantau:
  Partial Information Classes.
  SIGACT News, 34(1):32--46, 2003.
  Go to website | Show abstract
  
  In this survey we present partial information classes, which have been studied under different names and in different contexts in the literature. They are defined in terms of partial information algorithms. Such algorithms take a word tuple as input and yield a small set of possibilities for its characteristic string as output. We define a unified framework for the study of partial information classes and show how previous notions fit into the framework. The framework allows us to study the relationship of a large variety of partial information classes in a uniform way. We survey how partial information classes are related to other complexity theoretic notions like advice classes, lowness, bi-immunity, NP-completeness, and decidability.
• Till Tantau:
  Logspace Optimisation Problems and Their Approximation Properties.
  Technical report ECCC-TR03-077, Electronic Colloquium on Computational Complexity, 2003.
  Go to website | Show abstract
  
  This paper introduces logspace optimisation problems as an analogue of the widely studied polynomial-time optimisation problems. Similarly to the polynomial-time setting, logspace optimisation problems can have vastly different approximation properties, even though the underlying decision problems have the same computational complexity. In order to study the approximability of logspace optimisation problems in a systematic way, polynomial-time approximation classes are transferred to logarithmic space. Appropriate reductions are defined and optimisation problems are presented that are complete for these classes. It is shown that under the assumption L != NL some natural logspace optimisation problems cannot be approximated with a constant ratio; some can be approximated with a constant ratio, but do not permit a logspace approximation scheme; and some have a logspace approximation scheme, but cannot be solved in logarithmic space. An example of a problem of the latter type is the problem of finding the shortest path between two vertices of a tournament.
• Till Tantau:
  On Structural Similarities of Finite Automata and Turing Machine Enumerability Classes.
  Wissenschaft und Technik Verlag, 2003.
  Supervised by: Dirk Siefkes, Johannes Köbler. Disseration zum Dr. rer. nat., Technische Universität Berlin
  Show abstract
  
  There are different ways of measuring the complexity of functions that map words to words. Well-known measures are time and space complexity. Enumerability is another possible measure. It is used in recursion theory, where it plays a key role in bounded query theory, but also in resource-bounded complexity theory, especially in connection with nonuniform computations. This dissertation transfers enumerability to automata theory. It is shown that enumerability behaves similarly in recursion theory and in automata theory, but differently in complexity theory.

  The enumerability of a function f is the smallest m such that there exists an m-enumerator for f. An m-enumerator is a machine that produces, for every input word w, a set of up to m possibilities for f(w). By varying the parameter m and the class of allowed enumerators, different enumerability classes can be defined. In recursion theory, one allows arbitrary Turing machines as enumerators; in automata theory, only finite automata. A deep structural result that holds both for finite automata and for Turing machine enumerability is the following cross product theorem: if f × g is (n + m)-enumerable, then either f is n-enumerable or g is m-enumerable. In contrast, this theorem does not hold for polynomial-time enumerability.

  Enumerability can be used to quantify the difficulty of a language A by asking how difficult it is to enumerate its n-fold characteristic function \chi_Aⁿ and cardinality function #_Aⁿ. A language is (n, m)-verbose if \chi_Aⁿ is m-enumerable. The inclusion structures of Turing machine and of finite automata verboseness classes are identical: all (n, m)-Turing-verbose languages are (h, k)-Turing-verbose iff all (n, m)-fa-verbose languages are (h, k)-fa-verbose. The structure of polynomial-time verboseness classes is different.

  The enumerability of #_Aⁿ has been studied in detail in recursion theory. Kummer's cardinality theorem states that if #_Aⁿ is n-enumerable by a Turing machine, then A must be recursive. Evidence is gathered that this theorem also holds for finite automata: it is shown that the nonspeedup theorem, the cardinality theorem for two words, and the restricted cardinality theorem all hold for finite automata. The cardinality theorem does not hold for polynomial-time computations.

  The central proofs rely on two proof techniques that promise to be applicable in other situations as well: generic proofs and branch diagonalisation. Generic proofs use elementary definitions, a concept from logic, to define enumerators in terms of other enumerators. They can be instantiated for all computational models that are closed under elementary definitions. Examples of such models are finite automata, but also Presburger arithmetic and ordinal number arithmetic. The second technique is a new diagonalisation method, where machines are tricked on codes of diagonalisation decision sequences, rather than on codes of machines. Branch diagonalisation is not applicable universally, but where it is applicable, it can be used to diagonalise against Turing machines, using only finite automata.

  Results on enumerability classes have applications in unrelated areas, like finite automata protocol testing, classification problems where examples are provided, and separability. An intriguing example of such an application is the following theorem: if there exist regular supersets of A × A, A × \bar A, and \bar A × \bar A whose intersection is empty, then A is regular.

• Till Tantau:
  Query Complexity of Membership Comparable Sets.
  Theoretical Computer Science, 302(1-3):467-474, 2003.
  Go to website | Show abstract
  
  This paper investigates how many queries to k-membership comparable sets are needed in order to decide all (k+1)-membership comparable sets. For k >= 2 this query complexity is at least linear and at most cubic. As a corollary we obtain that more languages are O(log n)-membership comparable than truth-table reducible to P-selective sets.
• Till Tantau:
  Weak Cardinality Theorems for First-Order Logic.
  Technical report ECCC-TR03-024, Electronic Colloquium on Computational Complexity, 2003.
  Go to website | Show abstract
  
  Kummer's cardinality theorem states that a language is recursive if a Turing machine can exclude for any n words one of the n + 1 possibilities for the number of words in the language. It is known that this theorem does not hold for polynomial-time computations, but there is evidence that it holds for finite automata: at least weak cardinality theorems hold for finite automata. This paper shows that some of the recursion-theoretic and automata-theoretic weak cardinality theorems are instantiations of purely logical theorems. Apart from unifying previous results in a single framework, the logical approach allows us to prove new theorems for other computational models. For example, weak cardinality theorems hold for Presburger arithmetic.
• Till Tantau:
  Weak Cardinality Theorems for First-Order Logic.
  In Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT 2003), Volume 2751 of Lecture Notes in Computer Science, pp. 400-411. Springer, 2003.
  Go to website | Show abstract
  
  Kummer's cardinality theorem states that a language is recursive if a Turing machine can exclude for any n words one of the n + 1 possibilities for the number of words in the language. It is known that this theorem does not hold for polynomial-time computations, but there is evidence that it holds for finite automata: at least weak cardinality theorems hold for finite automata. This paper shows that some of the recursion-theoretic and automata-theoretic weak cardinality theorems are instantiations of purely logical theorems. Apart from unifying previous results in a single framework, the logical approach allows us to prove new theorems for other computational models. For example, weak cardinality theorems hold for Presburger arithmetic.

2002

• Lane A. Hemaspaandra, Proshanto Mukherji, Till Tantau:
  Computation with Absolutely No Overhead.
  Technical report URCS-TR-2002-779, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
  Go to website | Show abstract
  
  We study Turing machines that are allowed absolutely no space overhead. The only work space the machines have, beyond the fixed amount of memory implicit in their finite-state control, is that which they can create by cannibalizing the input bits' own space. This model more closely reflects the fixed-sized memory of real computers than does the standard complexity-theoretic model of linear space. Though some context-sensitive languages cannot be accepted by such machines, we show that a large subclasses of the context-free languages can even be accepted in polynomial time with absolutely no space overhead.
• Arfst Nickelsen, Till Tantau:
  On Reachability in Graphs with Bounded Independence Number.
  In Proceedings of the Eighth Annual International Computing and Combinatorics Conference (COCOON 2002), Volume 2387 of Lecture Notes in Computer Science, pp. 554--563. Springer, 2002.
  Show abstract
  
  We study the reachability problem for finite directed graphs whose independence number is bounded by some constant k. We show that this problem is first-order definable for all k. In contrast, the reachability problem for many other types of finite graphs, including dags and trees, is not first- order definable. We also study the reachability problem for succinctly represented graphs with independence number at most k. We also study the succinct version of the problem and show that it is \Pi^P₂-complete for all k.
• Mitsunori Ogihara, Till Tantau:
  On the Reducibility of Sets Inside NP to Sets with Low Information Content.
  Technical report URCS-TR-2002-782, Technische Berichtsreihe der Universität Rochester, Computer Science Department, 2002.
  Go to website | Show abstract
  
  We study whether sets inside NP can be reduced to sets with low information content but possibly still high computational complexity. Examples of sets with low information content are tally sets, sparse sets, P-selective sets and membership comparable sets. For the graph automorphism and isomorphism problems GA and GI, for the directed graph reachability problem GAP, for the determinant function det, and for logspace self-reducible languages we establish the following results:

  • If GA is \le^p_tt-reducible to a P-selective set, then GA \in P.
  • If GI is O(log)-membership comparable, then GI \in RP.
  • If GAP is logspace O(1)-membership comparable, then GAP \in L.
  • If det is \le^log_T-reducible to an L-selective set, then det \in FL.
  • If A is logspace self-reducible and \le^log_T-reducible to an L-selective set, then A \in L.

  The last result is a strong logspace version of the characterisation of P as the class of self-reducible P-selective languages. As P and NL have logspace self-reducible complete sets, it also establishes a logspace analogue of the conjecture that if SAT is \le^p_T-reducible to a P-selective set, then SAT \in P.
• Till Tantau:
  A Note on the Power of Extra Queries to Membership Comparable Sets.
  Technical report ECCC-TR02-044, Schriftenreihe der Institute für Informatik/Mathematik der Universität zu Lübeck, 2002.
  Go to website | Show abstract
  
  A language is called k-membership comparable if there exists a polynomial-time algorithm that excludes for any k words one of the 2^k possibilities for their characteristic string. It is known that all membership comparable languages can be reduced to some P-selective language with polynomially many adaptive queries. We show however that for all k there exists a (k+1)-membership comparable set that is neither truth-table reducible nor sublinear Turing reducible to any k-membership comparable set. In particular, for all k > 2 the number of adaptive queries to P-selective sets necessary to decide all k-membership comparable sets is Omega(n) and O(n³). As this shows that the truth-table closure of P-sel is a proper subset of P-mc(log), we get a proof of Sivakumar's conjecture that O(log)-membership comparability is a more general notion than truth-table reducibility to P-sel.
• Till Tantau:
  Comparing Verboseness for Finite Automata and Turing Machines.
  In Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Volume 2285 of Lecture Notes in Computer Science, pp. 465-476. Springer, 2002.
  Go to website | Show abstract
  
  A language is called (m,n)-verbose if there exists a Turing machine that enumerates for any n words at most m possibilities for their characteristic string. We compare this notion to (m,n)-fa-verboseness, where instead of a Turing machine a finite automaton is used. Using a new structural diagonalisation method, where finite automata trick Turing machines, we prove that all (m,n)-verbose languages are (h,k)-verbose, iff all (m,n)-fa-verbose languages are (h,k)-fa-verbose. In other words, Turing machines and finite automata behave in exactly the same way with respect to inclusion of verboseness classes. This identical behaviour implies that the Nonspeedup Theorem also holds for finite automata. As an application of the theoretical framework, we prove a lower bound on the number of bits needed to be communicated to finite automata protocol checkers for nonregular protocols.
• Till Tantau:
  Towards a Cardinality Theorem for Finite Automata.
  In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002), Volume 2420 of Lecture Notes in Computer Science, pp. 625-636. Springer, 2002.
  Go to website | Show abstract
  
  Kummer's cardinality theorem states that a language is recursive if a Turing machine can exclude for any n words one of the n+1 possibilities for the number of words in the language. This paper gathers evidence that the cardinality theorem might also hold for finite automata. Three reasons are given. First, Beigel's nonspeedup theorem also holds for finite automata. Second, the cardinality theorem for finite automata holds for n=2. Third, the restricted cardinality theorem for finite automata holds for all n.

2001

• Arfst Nickelsen, Till Tantau:
  Closure of Polynomial Time Partial Information Classes under Polynomial Time Reductions.
  In Proceedings of the 13th International Symposium on Fundamentals of Computation Theory (FCT 2001), Volume 2138 of Lecture Notes in Computer Science, pp. 299-310. Springer, 2001.
  Go to website | Show abstract
  
  Polynomial time partial information classes are extensions of the class P of languages decidable in polynomial time. A partial information algorithm for a language A computes, for fixed n, on input of words x₁, ..., x_n a set P of bitstrings, called a pool, such that \chi_A(x₁, ..., x_n) \in P, where P is chosen from a family D of pools. A language A is in P[D], if there is a polynomial time partial information algorithm which for all inputs (x₁, ..., x_n) outputs a pool P in D with \chi_A(x₁, ..., x_n) \in P. Many extensions of P studied in the literature, including approximable languages, cheatability, p-selectivity and frequency computations, form a class P[D] for an appropriate family D. We characterise those families D for which P[D] is closed under certain polynomial time reductions, namely bounded truth-table, truth-table, and Turing reductions. We also treat positive reductions. A class P[D] is presented which strictly contains the class P-sel of p-selective languages and is closed under positive truth-table reductions.
• Till Tantau:
  A Note on the Complexity of the Reachability Problem for Tournaments.
  Technical report ECCC-TR01-092, Electronic Colloquium on Computational Complexity, 2001.
  Go to website | Show abstract
  
  Deciding whether a vertex in a graph is reachable from another vertex has been studied intensively in complexity theory and is well understood. For common types of graphs like directed graphs, undirected graphs, dags or trees it takes a (possibly nondeterministic) logspace machine to decide the reachability problem, and the succinct versions of these problems (which often arise in hardware design) are all PSPACE-complete. In this paper we study tournaments, which are directed graphs with exactly one edge between any two vertices. We show that the tournament reachability problem is first order definable and that its succinct version is \Pi^P₂-complete.
• Till Tantau:
  Schnelle Löser für periodische Integralgleichungen mittels Matrixkompression und Mehrgitteriteration.
  Technische Universität Berlin, 2001. Diplomarbeit Mathematik
  Show abstract
  
  In this thesis we study fast solvers for a class of periodic integral equations. Such integral equations arise in a number applications, including the solution of Dirichlet problems and the biharmonic equation. The integrals employed in the integral equations under consideration are convolutions where a smooth distortion is allowed. Provided the fourier coefficients of the convolution kernels satisfy appropriate properties, the integral equations have unique solutions. Provided such a solution exists, we show how it can be found quickly. Here, "quickly" means with work proportional to the work needed to perform a fast fourier transformation. Using parallel hardware even logarithmic runtime can be achieved. To find solutions quickly, we proceed in three steps. First, all input functions are dicretised. Second, a spectral Galerkin method is applied to the resulting equations. The Galerkin method results in a large, but compressable system matrix. Third, the matrix compression allows us to use a multi-grid iteration. The iteration yields an asymptotically optimal approximation of the desired solution.

2000

• Klaus Didrich, Wolfgang Grieskamp, Florian Schintke, Till Tantau, Baltasar Trancón-y-Widemann:
  Reflections in Opal - Meta Information in a Functional Programming Language.
  In Proceedings of the 11th International Workshop on Implementation of Functional Languages, Lochem, The Netherlands, September 1999, (IFL'99), Selected Papers, Volume 1868 of Lecture Notes in Computer Science, pp. 146--164. Springer, 2000.
  Show abstract
  
  We report on an extension of the Opal system that allows the use of reflections. Using reflections, a programmer can query information like the type of an object at runtime. The type can in turn be queried for properties like the constructor and deconstructor functions, and the resulting reflected functions can be evaluated. These facilities can be used for generic meta-programming. We describe the reflection interface of Opal and its applications, and sketch the implementation. For an existing language implementation like Opal's the extension by a reflection facility is challenging: in a statically typed language the management of runtime type information seems to be an alien objective. However, it turns out that runtime type information can be incorporated in an elegant way by a source-level transformation and an appropriate set of library modules. We show how this transformation can be done without changing the Opal core system and causing runtime overhead only where reflections are actually used.
• Till Tantau:
  On the Power of Extra Queries to Selective Languages.
  Technical report ECCC-TR00-077, Electronic Colloquium on Computational Complexity, 2000.
  Go to website | Show abstract
  
  A language is selective if there exists a selection algorithm for it. Such an algorithm selects from any two words one, which is an element of the language whenever at least one of them is. Restricting the complexity of selection algorithms yields different selectivity classes like the P-selective or the semirecursive (i.e. recursively selective) languages. A language is supportive if k queries to the language are more powerful than k-1 queries for every k. Recently, Beigel et al. (J. of Symb. Logic, 65(1):1-18, 2000) proved a powerful recursion theoretic theorem: A semirecursive language is supportive iff it is nonrecursive. For restricted computational models like polynomial time this theorem does not hold in this form. Our main result states that for any reasonable computational model a selective language is supportive iff it is not cheatable. Beigel et al.'s result is a corollary of this general theorem since `recursively cheatable' languages are recursive by Beigel's Nonspeedup Theorem. Our proof is based on a partial information analysis (see Nickelsen, STACS 97, LNCS 1200, pp. 307-318) of the involved languages: We establish matching upper and lower bounds for the partial information complexity of the equivalence and reduction closures of selective languages. From this we derive the main results as these bounds differ for different k.

  We give four applications of our main theorem and the proof technique. Firstly, the relation E^P_k-tt(P-sel) \notsubseteq R^P_(k-1)-tt(P-sel) proven by Hemaspaandra et al. (Theor. Comput. Sci., 155(2):447-457, 1996) still holds if we relativise only the right hand side. Secondly, we settle an open problem from the same paper: Equivalence to a P-selective language with k serial queries cannot generally be replaced by a reduction using less than 2^k-1 parallel queries. Thirdly, the k-truth-table reduction closures of selectivity classes are (m,n)-verbose iff every walk on the n-dimensional hypercube with transition counts at most k visits at most m bitstrings. Lastly, these reduction closures are (m,n)-recursive iff every such walk is contained in a closed ball of radius n-m.