- 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:
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.
- 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".
- 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.
- 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_{2}^{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:
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.
- 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.
- 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.
- 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, 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.
- 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.
- 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.
- 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.
- 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:
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.
- 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, Ilka Schnoor, Till Tantau:
Influence of Tree Topology Restrictions on the Complexity of Haplotyping with Missing Data.
Theoretical Computer Science, 432:38–51, 2012.
Show PDF | Go to website | Show abstract
Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing, which is often the case in laboratory data, the resulting formal problem IPPH, which stands for incomplete perfect phylogeny haplotyping, is NP-complete. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP-complete; but here, at least, a fixed-parameter algorithm is known. Such drastic and ad hoc simplifications turn out to be unnecessary to make IPPH tractable: we present the first theoretical analysis of a parametrized algorithm, which we develop in the course of the paper, that works for arbitrary instances of IPPH. This tractability result is optimal insofar as we prove IPPH to be NP-complete whenever any of the parameters we consider is not fixed, but part of the input.
- Michael Elberfeld, Till Tantau:
Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
Information and Computation, 213:33–47, 2012.
Show PDF | Go to website | Show abstract
Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption.
- 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.
- 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.
- 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.