Mitarbeiterseminar

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $exp(Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $exp(Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting setting, which makes #ETH robust.

Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an $n     imes n$ matrix with $m$ nonzero entries requires time $exp(Omega(m))$. Restricted to 01-matrices, the bound is $exp(Omega(m/log m))$. Computing the Tutte polynomial of a multigraph with $n$ vertices and $m$ edges requires time $exp(Omega(n))$ at points $(x,y)$ with $(x-1)(y-1)
eq 1$ and $y
otin{0,pm 1}$. At points $(x,0)$ with $x
ot in {0,pm 1}$ it requires time $exp(Omega(n))$, and if $x=-2,-3,ldots$, it requires time $exp(Omega(m))$. For simple graphs, the bound is $exp(Omega(m/log^3 m))$.

This talk is a continuation of the Graduiertenkolleg lecture of June 28 on the same topic, but will be self-contained.

Derandomization constitutes a central theme in the theory of computing.
It involves the design of efficient deterministic simulations of randomized processes. Polynomial identity testing (PIT) is the fundamental problem of deciding whether a given polynomial identity holds. The problem has a natural and efficient randomized algorithm, but efficient deterministic algorithms for the general case have remained elusive.

In the lecture of June 28 we showed a hardness result for the general case. In this talk we will survey known positive results for special cases, present the key ingredients in the progress that has been made in the past few years, and show them at work in a simple setting.

A seminal technique of theoretical physics called Wick's theorem
interprets the Gaussian matrix integral of the products of the trace of
powers of Hermitian matrices as the number of labelled maps with a given
degree sequence, sorted by their Euler characteristics. This leads to the
map enumeration results analogous to those obtained by combinatorial
methods.

Martin Loebl and I showed that the enumeration of graphs embeddable on a
surface can be formulated as the Gaussian matrix integral of an ice-type
partition function, where the number of planar graphs appears as a leading
term.

In this talk I will consider a maximum flow generalization of the Shannon
Switching Game: Given is a network, which consists of a graph G with positive
integer capacities c on the edges, and two designated vertices s and t (the
source and sink). Two players, Maker and Breaker, alternatingly take turns
where they fix edges and delete edges which have not yet been fixed. The game
ends when all remaining edges are fixed. Maker wins iff in the remaining
network, a flow of a given value L can be sent from s to t. We consider the
decision problem that asks whether for a given network and integer L, Maker
has a winning strategy.

The Shannon Switching Game is the special case where L=1, and in this case the
problem can be decided in polynomial time, as was shown by Lehman (1964).

I will show that the general problem is PSPACE-hard, even in the special case
where G is a series-parallel (multi-)graph. In the case where every vertex of
G except possibly s and t has degree at most 3, the problem can be solved in
polynomial time. In the case of series-parallel graphs, I will discuss how
one can define and obtain approximation algorithms for this problem, and show
an interesting paradox that applies to more combinatorial games.

Das wohl wichtigste offene Problem im Bereich der deskriptiven
Komplexitätstheorie ist die Frage nach einer (handhabbaren) Logik, die
exakt alle in Polynomialzeit berechenbaren Klassen von Strukturen
charakterisiert. Sollte eine solche Logik nicht existieren, so würde
sich unmittelbar ergeben, dass die Komplexitätsklassen PTIME und NP
ungleich sind, da eine entsprechende logische Charakterisierung für NP
bekannt ist. Existiert eine solche Logik aber, dann ermöglicht diese
den Vergleich der beiden Komplexitätsklassen mit Methoden der
endlichen Modelltheorie. Außerdem würde eine solche Logik eine
Anfragesprache für Datenbanken implizieren, in der sich exakt alle
effizient (d.h. in Polynomialzeit) berechenbaren Anfragen ausdrücken
lassen, aber keine weiteren, was eine positive Antwort auf eine offene
Frage von Chandra und Harel aus dem Jahre 1982 wäre.

Mein Vortrag wird zunächst die grundlegenden Resultate in diesem
Bereich beleuchten. Vor deren Hintergrund ergeben sich zwei mögliche
Forschungsrichtungen, die eine Beantwortung der obigen Frage zum Ziel
haben und zu denen meine Dissertation einen Beitrag leistet: die
präzise Charakterisierung von PTIME auf eingeschränkten Klassen von
Strukturen, und der Entwurf von Logiken mit neuartigen
Ausdrucksstärken.

Im ersten Bereich erläutere ich meine Charakterisierung von PTIME auf
der Klasse der Intervallgraphen durch die Logik FP+C, die lediglich
einfache induktive Definitionen und Zählen beherrscht. Das Ergebnis
gibt Aufschluss über die Anwendbarkeit modularer Graphenzerlegungen
für die Kanonisierung von Graphenklassen. Aus dem Resultat ergibt sich
auch eine logische Charakterisierung der Komplexitätsklasse LOGSPACE
auf der Klasse der Einheitsintervallgraphen. Zudem wurden die
vorgestellten Techniken in einer gemeinsamen Arbeit mit Köbler,
Kuhnert und Verbitsky angewendet, um zu zeigen, dass
Intervallgraphenisomorphie und -kanonisierung mit nur logarithmischem
Platz möglich sind.

Im zweiten Bereich stelle ich logische Operatoren vor, die den Rang
von Matrizen über endlichen Körpern berechnen und so gewissermaßen
eine Verallgemeinerung der Fähigkeit zu zählen darstellen. Logiken mit
solchen Operatoren, sogenannte Ranglogiken, haben eine höhere
Ausdrucksstärke als FP+C, da sie alle bekannten Konstruktionen
ausdrücken können, die zeigen, dass FP+C schwächer ist als PTIME.
Somit sind Rangberechnungen eine intrinsische Fähigkeit von
Polynomialzeitalgorithmen, deren Verständnis für die Beantwortung der
ursprünglichen Frage wichtig ist. Neben grundlegenden Eigenschaften
von Rangoperatoren im logischen Kontext zeige ich, dass
Rangoperationen eine strikt größere Ausdrucksstärke haben bei
zunehmender Stelligkeit der betrachteten Matrizen. Schließlich schlage
ich eine Brücke zur klassischen Komplexitätstheorie, indem ich
erkläre, wie Variationen von Ranglogiken verschiedene
Komplexitätsklassen zwischen LOGSPACE und PTIME über der Klasse der
geordneten Strukturen charakterisieren. Die meisten dieser Ergebnisse
wurden in einer gemeinsamen Arbeit mit Dawar, Holm und Grohe
veröffentlicht.

Ein Petrinetz erzeugt auf natürliche Weise eine Sprache, nämlich die
Menge aller möglichen Schaltsequenzen, und einen Graph, nämlich seinen
Erreichbarkeitsgraph. Bei der Synthese von Petrinetzen geht es darum,
aus einer Sprache bzw. einen Graphen ein Petrinetz zu finden, das diese
Sprache bzw. diesen Graphen erzeugt.

In den 90er Jahren wurden erste Ergebnisse erzielt. Die treibenden
Kräfte Badouel, Bernadinello und Darondeau zeigten unter anderem, dass
die Synthese von Petrinetzen NP-hart ist.

Das von mir vorgestellte Paper von Darondeau (Unbounded Petri Net
Synthesis, LNCS 3098, 2004) behandelt die Synthese unbeschränkter
Petrinetze unter Einschränkung an die gegebene Sprache bzw. den
gegebenen Graph. Es stellt sich die Frage danach, wie stark diese
Einschränkungen sind. Diese Frage habe ich versucht zu beantworten und
habe bereits teilweise Antworten gefunden. Erstaunlich ist, dass die
Einschränkungen an die Sprache keine Einschränkungen zu sein scheinen,
d.h. Sprachen die von Petrinetzen erzeugt werden erfüllen die von
Darondeau in diesem Paper angesetzen Voraussetzungen.

In diesem Vortrag zeigen wir obere und untere Schranken für parametrisierte
Probleme innerhalb der Schaltkreiskomplexitätsklasse AC$^0$. Als erstes
Ergebnis in diese Richtung bewies Benjamin Rossman 2007, dass $k$-Clique
(enthält ein gegebener Graph eine Clique der Größe $k$?) AC$^0$-Schaltkreise der
Größe $n^{2k/9}$ benötigt. Kazuyuki Amano konnte 2009 die Methode auf
Subgraphisomorphieprobleme erweitern. Darauf aufbauend zeigen wir untere
Schranken für induzierte Subgraphisomorphie- und Homomorphieprobleme.

Mit einer auf Schaltkreise übertragenen fpt-Reduktion folgt, dass die
$k$-Clique-Schranke auch für $k$-DominatingSet gilt. Auf der anderen Seite können
wir zeigen, dass sich $k$-VertexCover mit $f(k)n^2$ Gattern in AC$^0$ berechnen
lässt.

In this talk we will present a polynomial time algorithm for computing
flat and linkless embeddings of graphs in $mathbb R^3$.

An embedding of a graph in 3-dimensional space is called "linkless" if
no pair of disjoint cycles forms a non-trivial link in the sense of
knot-theory. That is, for any two disjoint cycles in the embedding,
one can be contracted to a single point without cutting the other. A
graph is called linklessly embeddable if it has a linkless embedding
in $mathbb R^3$.

Linklessly embeddable graphs generalise the concept of planar graphs
to the 3-dimensional case. Like planar graphs, they have many nice
properties which makes it desirable to decide whether a graph is
linklessly embeddable and if so, to compute an embedding.

Not every graph has a linkless embedding, though. A characterisation
in terms of excluded minors of those graphs that can be drawn in this
way was given by Robertson, Seymour and Thomas, generalising the
characterisation of planar graphs by Kuratowski and Wagner. However,
while this can be used to decide whether a graph has a linkless
embedding, this does not give an algorithm for actually computing one
if it exists.

In this talk I will present such an algorithm for computing linkless
embeddings. In fact, we will compute even nicer embeddings which are
called flat.

I will first introduce the relevant concepts needed for the algorithm
and then present the main ideas focussing mostly on the
graph-theoretical aspects of the algorithm.

Beim Datenaustausch sollen Daten (hier relationale Daten) von einem Format in ein anderes Format gemäß einer vorgegebenen Spezifikation (hier durch eine Menge logischer Formeln) transformiert werden. Anfrageauswertung bezeichnet in diesem Kontext das Problem der Beantwortung von Anfragen, die über das Zielformat "sprechen" (d.h. Anfragen an das Resultat des Datenaustauschs). Dieses Problem ist insofern interessant, als das Resultat des Datenaustauschs üblicherweise nicht vollständig spezifiziert wird und es daher mehr als eine Möglichkeit geben kann, Daten ins Zielformat zu übersetzen. Ein weiteres Problem besteht darin, dass einige Informationen über das Resultat des Datenaustauschs oft nur implizit spezifiziert werden. Die grundlegende Frage ist dann, wie solche Anfragen überhaupt beantwortet werden sollen bzw. können.

Eine erste Anfragesemantik wurde 2003 von Fagin, Kolaitis, Miller und Popa vorgestellt und wurde schnell als die "richtige" Semantik zur Auswertung monotoner Anfragen (wie z.B. konjunktive Anfragen) akzeptiert. Darüberhinaus hat sich aber gezeigt, dass sie für nicht-monotone Anfragen oft unintuitive Antworten liefert. Der Vortrag gibt eine kurze Übersicht über einige in der Literatur vorgestellte Semantiken für nicht-monotone Anfragen und wendet sich dann der Komplexität der Anfrageauswertung bzgl. einer konkreten Semantik zu. Insbesondere wird ein Algorithmus zur Auswertung sogenannter universeller Anfragen bzgl. passend eingeschränkten Spezifikationen skizziert, der für die im Datenaustausch übliche Einschränkung, dass die Spezifikation und die Anfrage fest ist, in Polynomialzeit arbeitet. Dieses Resultat ist insofern überraschend, als dass die Auswertung nicht-monotoner Anfragen üblicherweise coNP-schwer bzw. unentscheidbar ist.

Theoretical computer science provides us with tools and techniques to
classify problems as efficiently solvable or computationally hard. But
even hard problems have to be solved and there exist various ways to
attack them. One way is to restrict the input to certain classes that
are computationally more feasible. In the case of graph theoretic
problems, this is akin to considering the problem on special graph
classes. One of the most important such classes is the class of
planar graphs or more generally, graphs that are embedded on a fixed
surface; an even further generalization is to consider classes of
graphs that are closed under taking minors. Such classes of graphs
have been extensively studied in the past three decades, especially
due to the deep graph minor theory of Robertson and Seymour. In this
thesis, we consider various algorithms on or related to such graph
classes and the theory of graph minors. The thesis consists of three
parts:

In the first part, we consider the Steiner tree problem in embedded
graphs. We present an extension, engineering, and application of the
recent polynomial-time approximation scheme (PTAS) of this problem in
planar graphs by Borradaile, Klein, and Mathieu (2007,2009): (i) we
show how to generalize the technique of the PTAS from planar graphs to
graphs of bounded genus and further subset connectivity problems; (ii)
we implemented and engineered this algorithm from a practical point of
view and show that it works surprisingly well, even on very large
instances; and (iii) we apply this algorithm to obtain an efficient
PTAS for the geometric Steiner tree problem among obstacles in the
plane.

In the second part of the thesis, we present a linear-time
shortest-paths algorithm for proper minor-closed graph classes and
show how to obtain faster approximation schemes and parameterized
algorithms for various problems on these graphs classes.

Finally, in the last part, we provide the first lower bounds for
Courcelle's famous theorem (1990) about the model-checking problem of
fixed formulas of monadic second-order logic in graphs. Whereas
Courcelle showed that this problem is efficiently solvable on graphs
of bounded treewidth, we show that on various classes of graphs of
unbounded but low treewidth the problem becomes computationally hard
(modulo some complexity assumptions). Along the way, we develop
several algorithmic tools using recent graph structure theory: most
notably, we provide polynomial-time algorithms to construct brambles,
grid-like minors, and tree-ordered webs in general graphs of high
enough treewidth.

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We generalize the problem of finding, for a given width-function, the width of a Hypergraph together with a corresponding optimal tree decomposition. This covers the problems of generalized and fractional hypertree-width by using suitable width-functions. We develop a first exact exponential algorithm for this problem. Showing the connection with tree decompositions of graphs, we adapt known combinatorial and algorithmic results of the latter and provide a notably enhanced algorithm.

The currently fastest deterministic algorithm for k-SAT is based on deterministic local search, introduced by Dantsin et al. (2002). Basically the same algorithm can also be used to solve (d,k)-CSPs (constraint satisfaction problems), which are the same as CNF formulas, but with d instead of 2 'truth values'.

In the talk, I will present this algorithm and show a surprisingly simple way to substantially improve its running time. The idea is to change the notion of Hamming distance, thus changing the neighborhood relation between assignments (colorings) and the notion Hamming balls.