Title: Complexity results and algorithms for Multicut on graphs of bounded clique-width
Language: English
Authors: Lackner, Martin 
Qualification level: Diploma
Keywords: Parametrisierte Komplexitätstheorie; FPT; Cliquenweite; Baumweite; Komplexitätstheorie; NP-vollständig; Logik; Graphen; Multicut; Algorithmen
Parameterized Complexity Theory; FPT; Clique-width; Tree-width; Complexity theory; NP-complete; Logic; Graphs; Multicut; Algorithms
Advisor: Pichler, Reinhard 
Issue Date: 2010
Number of Pages: 88
Qualification level: Diploma
Abstract: 
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.

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.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-44603
http://hdl.handle.net/20.500.12708/11570
Library ID: AC07808541
Organisation: E184 - Institut für Informationssysteme 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

11
checked on Feb 21, 2021

Download(s)

70
checked on Feb 21, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.