Mitarbeiterseminar Logik in der Informatik

Wir führen eine alternative Charakterisierung der Komplexität von Graphen ein und zeigen deren Äquivalenz zur klassischen Baumweite. Über eine Rekursionsformel für diese Charakterisierung entwickeln wir dann einen rekursiven Algorithmus zur exakten Baumweitenberechnung.

Für praktische Anwendungen sind Heuristiken zur Bestimmung von Schranken für die Baumweite jedoch deutlich besser geeignet, da ansonsten enorm hohe Laufzeiten zu erwarten sind. Wir betrachten einige ausgewählte Ergebnisse von umfangreichen Berechnungen auf Zufallsgraphen sowie verschiedenen praktischen Graphinstanzen.

Partitionsfunktionen stammen ursprünglich aus der statistischen Physik und sind die fundamentalen Größen mit denen sich Phasenübergänge in komplexen physikalischen Systemen beschreiben lassen. Viele Partitionsfunktionen lassen sich als gewichtete Homomorphismenprobleme auf Graphen darstellen wodurch ihre enge Verwandschaft mit einer Reihe wichtiger Graphinvarianten offenbar wird. Beispiele hierfür sind die Zahl der stabilen Knotenmengen eines Graphen und die Zahl der k-Färbungen.

Die Untersuchung der Komplexität dieser Funkionen, erlaubt also eine vereinheitlichende Beschreibung der Komplexität vieler wichtiger Berechnungsprobleme der statistischen Physik und Graphentheorie. In den vergangenen Jahren sind eine Reihe von Arbeiten zu diesem Thema erschienen, die den Kenntnisstand sukzessive verallgemeinert haben. In meinem Vortrag werde ich eines der derzeit allgemeinsten Resultate vorstellen.

We introduce a simple, yet very effective, technique to obtain (sub)-exponential fixed-parameter algorithms on graphs of bounded local treewidth or excluding a fixed graph H as a minor, such as planar graphs, bounded-genus graphs, or linklessly embeddable graphs. Our algorithm has the curious running time of O*(2^sqrt{k log n}), where n is the size of the input and k is the number of vertices or edges in the solution. For *any* c > 0, this running time is at most O(2^(k/c) + n^c). It follows that: any problem that admits our technique (i) can be solved in O*((1+epsilon)^k)-FPT time for any epsilon > 0; (ii) can be solved in true Subexponential FPT time if it admits any subexponential kernel. Our technique can be directly applied to a variety of problems, such as Steiner tree, (directed) subgraph isomorphism, (directed) subgraph with a property, (directed) longest path, vertex cover, independent set, dominating set, and many more. Also, for some problems one can still apply some variation of our technique; we demonstrate this on the example of the maximum-leaf spanning tree problem.

Klassische Approximierbarkeit und parametrische Komplexitätstheorie verfolgen beide das Ziel, schwere (NP-harte) Probleme handhabbar zu machen. Nichtsdestotrotz existieren Probleme wie das disjunkte Kreiseproblem für gerichtete Graphen, die sich diesen Versuchen widersetzen. Ich definiere parametrische Approximierbarkeit, um solch "hartnäckige" Probleme zu attackieren. Ich werde den Begriff der fpt Approximationsalgorithmen einführen und Varianten dieser Definition vorstellen. Neben ersten Approximierbarkeits- und Nichtapproximierbarkeitsergebnissen für diese neue Klasse von Approximationsalgorithmen werde ich darauf eingehen, dass das disjunkte Kreiseproblem als ein natürliches, schweres Problem fpt approximierbar ist. Schließlich werde ich die Ergebnisse auf eine Variante des disjunkten Pfadeproblems in gerichteten Kreisen übertragen und weitere effizient lösbare Spezialfälle dieses Problems vorstellen.

In this talk I will overview the very recent results obtained by Daniel Marx, Barry O'Sullivan and myself. In particular our main technical result states that given a graph $G$, terminals $s$ and $t$, and a parameter $k$, there is an FPT algorithm that transforms $G$ into another graph $G^*$ of treewidth depending on $k$ that retains all minimal $s-t$ separators of size at most $k$. Moreover, the subgraphs of $G$ and $G^*$ induced by each of these separators are isomorphic.

We observe that for many constrained separation problems the above result enables transformation from the original instance to the instance with a restricted treewidth and that this allows to show the fixed-parameter tractability of these problems by applying the well known Courcelle's theorem. Moreover, using the transformation proposed by Reed et al., this technique can be extended to the constrained bipartization problems.

To demonstrate the power of the above methodology, we resolve a number of open problems in the area of parameterized complexity. For example, we show that the problem of checking existence of an independent set of size exactly $k$ whose removal makes the graph bipartite is FPT thus resolving an open problem posed in 2001 by Diaz et al (MFCS 2001).

The above overview will be preceded by a very brief introduction to the area of parameterized complexity and an intuitive description of the Courcelle's Theorem in order to make the talk accessible to a general Theoretical Computer Science audience that is not necessary familiar with this machinery.

The paper presenting the results covered by the talk is available at:
<a href="http://arxiv.org/PS_cache/arxiv/pdf/0902/0902.3780v1.pdf">http://arxiv.org/PS_cache/arxiv/pdf/0902/0902.3780v1.pdf</a>

Arc consistency is a basic reasoning technique in constraint satisfaction for efficiently detecting unsatisfiable instances, in a sound but incomplete way. Although incomplete in general, it is known that arc consistency solves the constraint satisfaction problem on certain constraint languages. In this talk, I will give an overview of a line of work that studies arc consistency and extensions thereof. In particular, we attempt to characterize, for each algorithm, the constraint languages on which the algorithm works. For many of these algorithms, algebraic characterizations of the solvable languages can be obtained; these highly facilitate understanding the power, limitations, and robustness of these algorithms.

Joint work with Berit Grussien, Manuel Bodirsky, and Victor Dalmau.