[Back]

M. Lackner:
"Complexity results and algorithms for Multicut on graphs of bounded clique-width";
Supervisor: R. Pichler; Institut für Informationssysteme, 2010; final examination: 2010-09-30.

Multicut is an extensively studied problem in the area of algorithms on graphs. It plays an important role in different fields such as circuit design or network theory. A Multicut problem is given by a graph G and the so-called terminal set which contains pairs of vertices. The aim is to find a minimal cut that separates all terminal pairs. However, even on simple graphs such as trees, Multicut is NP-complete.
Often it is not just the size of the input that makes a problem computationally hard, but certain properties of the input. These properties are used as parameters for a more detailed analysis of hard problems. Such a parameterized complexity analysis sometimes leads to fixed parameter tractable (FPT) algorithms, which are especially efficient when a certain parameter is small. A number of recent results have found tractable fragments of Multicut. Especially tree-width has proven to be a useful parameter. However there is a clear drawback of FPT algorithms via tree-width: the graph has to be sparse.
The goal of this thesis is to systematically study Multicut on graphs of bounded clique-width. Clique-width is a graph complexity measure similar to tree-width, but it can be small for both sparse and dense graphs. We present an efficient, fixed-parameter tractable algorithm with the size of the terminal set and the clique-width of G as parameter. Furthermore an extensive complexity analysis of Multicut on graphs of bounded clique-width establishes boundaries of this approach.
We also present an extension of a metatheorem about graphs of bounded clique-width by Courcelle et al. Our extension is applicable to arbitrary structures where the clique-width of their incidence graphs is bounded. Finally we prove that a class of graphs has bounded tree-width if and only if their incidence graphs have bounded clique-width.

Multicut ist ein viel untersuchtes Problem aus dem Gebiet der Algorithmen auf Graphen. Es hat große Bedeutung in verschiedensten Gebieten, wie zum Beispiel beim Schaltungsentwurf oder in der Netzwerktheorie. Ein Multicut-Problem ist durch einen Graphen G und die so genannte Terminalmenge gegeben, die Paare von Knoten enthält. Das Ziel des Multicut-Problems ist es, alle Knotenpaare in der Terminalmenge durch Schnitte im Graphen zu trennen. Dies ist ein Problem mit hoher Rechenkomplexität, da Multicut schon auf Bäumen NP-vollständig ist.
In vielen Fällen ist es nicht nur die Größe der Eingabe, die ein Problem rechnerisch komplex macht, sondern spezielle Eigenschaften der Eingabe.
Diese Eigenschaften der Eingabe werden als Parameter für eine detailliertere Untersuchung von Problemen mit hoher Rechenkomplexität verwendet. Solch eine parametrisierte Komplexitätsanalyse führt manchmal zu parametrisierbaren Algorithmen (kurz: FPT-Algorithmen), die besonders effizient sind, wenn bestimmte Parameter klein sind. In mehreren Publikation wurden bereits FPT-Algorithmen für Multicut gefunden.
Hierbei hat sich die Baumweite als besonders geeigneter Parameter herausgestellt. Allerdings haben auf Baumweite basierende FPT-Algorithmen einen klaren Nachteil: Sie funktionieren nur für Graphen mit wenigen Kanten.
Das Ziel dieser Arbeit ist es, für Multicut eine systematische Untersuchung in Bezug auf Graphen mit beschränkter Cliquenweite durchzuführen. Cliquenweite ist ein Komplexitätsmaß für Graphen ähnlich zur Baumweite mit dem bedeutenden Unterschied, dass sie auch klein für dichte Graphen sein kann. In dieser Arbeit präsentieren wir einen effizienten FPT-Algorithmus mit der Kardinalität der Terminalmenge und der Cliquenweite von G als Parameter. Darüber hinaus zeigen wir mit einer umfangreichen Komplexitätsanalyse Grenzen dieses Ansatzes auf.
Wir präsentieren auch eine Erweiterung des Cliquenweite-Metatheorems von Courcelle et al. über Graphen mit beschränkter Cliquen- weite. Abschließend beweisen wir noch, dass eine Klasse von Graphen genau dann beschränkte Baumweite hat, wenn ihre Inzidenzgraphen beschränkte Cliquenweite haben.