Algorithm design techniques for parameterized graph modification problems [Elektronische Ressource] / von Jiong Guo

Sujets

• Informatik
• Mathematics

Informations

• Publié par: friedrich-schiller-universitat_jena
• Publié le: 01 janvier 2006
• Nombre de lectures: 28
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Algorithm Design Techniques for
Parameterized Graph Modification
Problems
Dissertation
zur Erlangung des akademischen Grades
doctor rerum naturalium (Dr.rer.nat.)
vorgelegt dem Rat der Fakult¨at fu¨r Mathematik und Informatik
der Friedrich-Schiller-Universit¨at Jena
von Dipl.-Inform. Jiong Guo
geboren am 28.11.1970 in Chengdu, V. R. ChinaGutachter
1. Prof. Rolf Niedermeier (Friedrich-Schiller-Universita¨t Jena)
2. Prof. Michael R. Fellows (The University of Newcastle, Australien)
3. Prof. Michael A. Langston (University of Tennessee, USA)
Tag der letzten Pru¨fung des Rigorosums: 9. Feb. 2006
Tag der o¨ffentlichen Verteidigung: 16. Feb. 2006Erk¨arung
Hiermiterkla¨reich,dassichdieArbeitselbst¨andigundnurmitdenangegebe-
nen Hilfsmitteln angefertigt habe.
Jena, April 2005 Jiong Guo5
Zusammenfassung
DieseArbeitbescha¨ftigtsichmitdemEntwurfparametrisierterAlgorithmen
fu¨r Graphmodifikationsprobleme wie Feedback Vertex Set, Multicut in
Trees,Cluster Editing,Closest 3-Leaf Power undMulticommodity
Demand Flow in Trees.
GraphensindheutzutageeinweitverbreitetesundoftverwendetesWerkzeug
zur Modellierung komplexer Beziehungen zwischen einzelnen Objekten. Basie-
rend auf solchen Graphmodellierungen k¨onnen viele in der Praxis auftretende
Probleme, die andernfalls nur sehr schwer zug¨anglich sind, in einer anschauli-
chen und mathematisch pra¨zisen Form dargestellt werden. Da es sich bei vie-
len praxisbezogenen Problemen um Fehlerkorrektur, Konfliktvermeidung und
Umstrukturierung handelt, sind Graphmodifikationsprobleme ein fundamenta-
ler Bestandteil der algorithmischen Graphentheorie. Grob gesagt haben solche
¨Probleme als Eingabe einen Graphen, fu¨r den eine minimale Anderung durch
Lo¨schungvonKnotenundKantenundEinfu¨gungvonKantengesuchtist,damit
der gea¨nderte Graph eine bestimmte Eigenschaft hat.
Aufgrund der NP-Vollstandigkeit der meisten Graphmodifikationsprobleme¨
stellt die Approximation einer optimalen Losung den am meisten gebrauch-¨
ten L¨osungsansatz dar. Seit Anfang der 90er Jahre des letzten Jahrhunderts
entwickelten sich parametrisierte Algorithmen zu einer sinnvollen und ernstzu-
nehmenden Alternative zu Approximationsalgorithmen beim Lo¨sen NP-harter
Graphmodifikationsprobleme. Die Grundidee dieses algorithmischen Ansatzes
ist die Identifizierung impliziter und expliziter Problemparameter, auf welche
die kombinatorischeExplosion“, die bei der algorithmische Behandlung harter
”
Probleme auftritt, beschr¨ankt werden kann. Sind die Parameter klein, was in
vielen praktischen Anwendungen der Fall ist, kann mit einer beweisbar guten
Laufzeit des Lo¨sungsalgorithmus gerechnet werden. Damit lassen sich optima-
le L¨osungen harter Probleme oftmals in einem praktisch ertra¨glichen Zeitraum
berechnen.
Diese Arbeit untersuchtdieAnwendbarkeitvonvierTechnikenzurEntwick-
lung parametrisierter Algorithmen im Bereich von Graphmodifikationsproble-
men.DarunterbefindensichzweiklassischeTechniken,namlichDatenreduktion¨
und tiefenbeschrankte Suchbaume, und zwei neue Techniken, namlich iterative¨ ¨ ¨
Kompression und Parametrisierung durch die Distanz von einer Trivialitat“.¨
”
Jeder der Techniken ist ein eigener Teil dieser Arbeit gewidmet. Im Folgenden,
ein Graph G =(V,E) besteht aus einer Menge von Knoten V und einer Menge
Kanten E. Die Anzahl der Knoten bezeichnen wir mit n (|V| =n), die Anzahl
der Kanten mit m (|E| =m).
Teil 1 enthalt eine kurze Einfuhrung in Graphmodifikationsprobleme und¨ ¨
¨eine Ubersicht der verwendeten Notationen und Grundbegriffe aus der Gra-
phentheorie. Dieser Teil wird durch eine ausfuhrliche Zusammenfassung von¨6
Ergebnissen dieser Arbeit abgeschlossen.
Teil 2 befasst sich mit der im Jahr 2004 eingefuhrten Technik der soge-¨
nannten iterativen Kompression, die mit einem sehr einfachen Teilgraphen ei-
nesgegebenen Graphenanfangtund induktiv immergroßerereTeilgraphenauf-¨ ¨
bautbis derEingabegrapherreichtwird.Im Laufedesinduktiven Aufbauswird
zunachsteine großereLosungberechnet und dann durch eine Kompressionspro-¨ ¨ ¨
zedur wieder zu einer kleineren komprimiert“. Kapitel 2 stellt die Grundidee
”
von iterativer Kompression vor und analysiert deren Anwendbarkeit fur Gra-¨
phmodifikationsprobleme. Das eingefu¨hrte Entwurfschema fu¨r die Anwendung
dieser Technik, bestehend aus Iterationsprozedur und Kompressionsprozedur,
ko¨nnte fu¨r ku¨nftige Forschungen im Bereich dieser Technik eine gute Basis bil-
den.
Kapitel 3 befasst sich mit einem klassischen Graphmodifikationsproblem,
FeedbackVertexSet(FVS).Diesesfragtfu¨reinengegebenenGraphennach
einer Menge von ho¨chstens k Knoten, deren Entfernung aus dem Graphen alle
seine Kreisezersto¨rt.Dieses Problemfindet Anwendung in vielen Bereichenwie
etwa Bioinformatik und ku¨nstlicher Intelligenz. Basierend auf iterativer Kom-
pression zeigen wir hier einen parametrisierten Algorithmus fu¨r FVS in Bezug
k 2auf den Parameter k, dessen Laufzeit O(c ·m ) fu¨r eine Konstante c betra¨gt.
Dies erlaubt es, eine lange Zeit offene Frage aus der parametrisierten Komple-
1xita¨tstheorie zu beantworten.
In Kapitel 4 fuhren wir zwei allgemeine Beschleunigungsmethoden fur itera-¨ ¨
tive Kompression ein. Als ein Beispiel fur die Anwendung der ersten Beschleu-¨
nigungsmethode betrachten wir das Edge Bipartization Problem: fur einen¨
gegebenen Graphen wird eine Menge von hochstens k Kanten gesucht, deren¨
Loschung den Graphen in einen bipartiten Graphen transformiert. Wir verbes-¨
k 3 2sern die bisher beste Laufzeitschranke fur dieses Problem von O(3 ·k ·m ·n)¨
k 2auf O(2 ·m ). Mit der zweiten Beschleunigungsmethode erreichen wir einen
kzweiten Algorithmus fur FVS mit einer Laufzeit von O(c ·m). Dies bedeutet,¨
dassFVSfurkonstantenParameterinLinearzeitlosbarist,eineEigenschaftdie¨ ¨
bislang nur fur wenige parametrisierte Probleme gezeigt werden konnte.¨
Das letzte Kapitel von Teil 2 erweitert das Anwendungsgebiet der iterati-
ven Kompression um alle minimalen Losungen fur ein Problem berechnen zu¨ ¨
kkonnen. Das Hauptergebnis ist ein Aufzahlungsalgorithmus, der in O(c ·m)¨ ¨
Zeit alle minimalen Lo¨sungen fu¨r FVS in einem gegebenen Graphen aufza¨hlt,
welche nicht mehr alsk Knoten enthalten. Der Algorithmus ist zudem der erste
Aufza¨hlungsalgorithmus der auf iterativer Kompression basiert.
Datenreduktion und Problemkerne sind das Thema von Teil 3. Dabei wird
versucht, die Eingabeinstanz auf eine neue, kleinere Instanz zu reduzieren“.
”
Die kleinere Instanz wird als Problemkernbezeichnet. Um die Grundidee dieser
Technik zu erkla¨ren, rekapitulieren wir die klassische Buss-Datenreduktion“,
”
die zu einem Problemkern fu¨r Vertex Cover fu¨hrt. Außerdem zeigen wir in
einer Fallstudie einen Problemkernfu¨r dasMinimum Clique Cover Problem,
1 Das Ergebnis wurde auch unabhangig von Dehne et al. gezeigt [52].¨7
2welcher die parametrisierte Handhabbarkeit dieses Problems impliziert.
Kapitel 7 pra¨sentiert einen Problemkern fu¨r das Cluster Editing Pro-
blem, das fur einen gegebenen Graphen nach einer Menge von hochsten k Kan-¨ ¨
tenmodifikationen sucht, die den Eingabegraph in eine Menge von disjunkten
2vollst¨andigen Teilgraphen transformieren. Der Problemkern besteht aus O(k )
Knoten, wobei k die Anzahl der ben¨otigten Kantenmodifikationen ist, und ba-
siertaufzweiDatenreduktionsregeln.AngeregtdurchunserErgebnisuntersuch-
te Damaschke [50] einen full problem kernel“ fu¨r die Aufza¨hlungsvariante von
”
Cluster Editing.
Das Hauptresultat von Kapitel 8 ist der Nachweis der Existenz eines Pro-
blemkerns fur das Multicut in Trees Problem. Multicut in Trees wurde¨
sehrausfuhrlichimKontextderApproximationsalgorithmeninderLiteraturun-¨
tersucht. Das Problem kommt im Bereich des Netzwerkentwurfs vor und sucht
nach einer Menge von Kanten in einem Baumnetzwerk, deren Loschung vor-¨
gegebene Knotenpaare voneinander trennt. Acht einfache und leicht zu imple-
mentierendeReduktionsregelnwerdengegeben;derBeweisfurdenProblemkern¨
erweist sich allerdings als technisch aufwandig.¨
Teil 4 besch¨aftigt sich mit tiefenbeschra¨nkten Suchba¨umen, der wohl am
h¨aufigsten angewandten Methode fu¨r den Entwurf von parametrisierten Al-
gorithmen. Die entscheidende Idee hierbei ist ein vollsta¨ndiges Absuchen des
Lo¨sungsraumes, das nach einer Baumstruktur systematisch organisiert wird.
Bezu¨glich Graphmodifikationsproblemen konzentrieren wir uns in Kapitel 9 auf
ein allgemeines Schema zum Entwurf parametrisierterAlgorithmen fu¨r die Pro-
bleme, die auf eine sogenannte Charakterisierung durch verbotene Teilgraphen
zuru¨ckzufu¨hrensind. Der Schwerpunkt derUntersuchungliegt auf solchen Cha-
rakterisierungen, die unendlich viele verbotene Teilgraphen enthalten. Um die-
ses Schema fu¨r den Entwurf von Suchbaumalgorithmen mit Hilfe verbotener
Teilgraphen zu erl¨autern, geben wir einen einfachen Suchbaumal