Beyond perfection [Elektronische Ressource] : on relaxations and superclasses / von Annegret K. Wagler

Sujets

• Mathematics

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2007
• Nombre de lectures: 17
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Beyond Perfection:
On Relaxations and Superclasses
H a b i l i t a t i o n s s c h r i f t
zur Erlangung des akademischen Grades
doctor rerum naturalium habilitatus (Dr. rer. nat. habil.)
genehmigt
durch die Fakult¨at fu¨r Mathematik
der Otto-von-Guericke-Universita¨t Magdeburg
von Dr. rer. nat. Annegret K. Wagler
geb. am 04.12.1968 in Leipzig
Gutachter:
Prof. Dr. Martin Gro¨tschel
Prof. Dr. Thomas Liebling
Prof. Dr. Robert Weismantel
Magdeburg, den 10.01.2007iiZusammenfassung
Perfekte Graphen, Anfang der 1960er Jahre von Claude Berge eingefu¨hrt,
bilden eine Graphenklasse mit reichen strukturellen Eigenschaften. Charak-
terisierungen perfekter Graphen bezu¨glich so verschiedener Konzepte wie
• F¨arbungen von Graphen,
• Additivit¨at der Graph-Entropie,
• Ganzzahligkeit von Polytopen,
verdeutlichen diese besonderen Eigenschaften und bilden gleichzeitig eine
Schnittstelle zwischen den Gebieten Graphentheorie, Informationstheorie,
Kombinatorischer Optimierung, Ganzzahliger Programmierung und Polye-
dertheorie, siehe Sektion 1.1.
Leider sind die meisten Graphen nicht perfekt und besitzen keine solche
herausragendenEigenschaften. Esistdaherinteressantzuerforschen,welche
Graphenzumindesthinsichtlich einiger Eigenschaften ‘fastperfekt’sindund
wie man diese N¨ahe zu Perfektheit messen kann. Wir relaxieren dafu¨r den
Perfektheitsbegriff bezu¨glich oben genannter Konzepte und untersuchen die
so erhaltenen Oberklassen perfekter Graphen sowie verschiedene Wege, um
den Grad von Imperfektheit auszudru¨cken.
F¨arbungen von Graphen. Das F¨arben der Knoten von Graphen ist
ein wichtiges Konzept mit vielfa¨ltigen Anwendungen, das Bestimmen der
F¨arbungszahl χ(G) eines Graphen ist jedoch i.a. NP-schwer. Die Cliquen-
zahlω(G)isteinenatu¨rlicheuntereSchrankefu¨rχ(G); fu¨rperfekteGraphen
G gilt stets Gleichheit (fu¨r alle induzierten Untergraphen), im Allgemeinen
k¨onnen die beiden Parameter jedoch beliebig weit auseinander liegen [70].
Eine natu¨rliche Frage ist also, fu¨r welche Graphenklassen die Differenz zwi-
schenCliquenzahlω(G)undF¨arbungszahlχ(G)unterKontrolleist. Wirbe-
scha¨ftigen uns mit zwei Konzepten, um diese Frage zu beantworten: oberen
Schranken fu¨r χ(G) als Funktion von ω(G) und dem Imperfektheitsgrad
eines Graphen.
iiiiv
′Eine Graphenklasse G ist χ-bound mit Bindingfunktion b, falls χ(G)≤
′ ′b(ω(G)) fu¨r alle induzierten Untergraphen G von Graphen G∈G gilt [51].
Perfekte Graphen sind genau die Graphen mit Bindingfunktion b(x) = x
und Klassen mit linearer Bindingfunktion b(x) =bx+c haben ¨ahnlich gute
F¨arbungseigenschaften. Wir untersuchen in Kapitel 2 verschiedene Klassen
mit Bindingfunktion b(x) =x+1.
Gerke und McDiarmid fu¨hrten in [45] als ¨ahnliches Konzept den Imper-
fektheitsgrad eines Graphen G ein als
χ (G,c)f
imp(G) = max | c :V(G)→N\{0}
ω(G,c)
(G,c) die fraktionale gewichtete F¨arbungszahl und ω(G,c) die ge-wobei χf
wichtete Cliquenzahl ist. Jeder perfekte Graph G hat imp(G) = 1 und
alle Graphen mit einem kleinen Imperfektheitsgrad k¨onnen als ‘fast per-
fekt’ angesehen werden. Wir geben fu¨r einige Klassen obere Schranken fu¨r
den Imperfektheitsgrad an, siehe Sektion 5.2. Weiter leiten wir fu¨r Klassen
mit unbeschra¨nktem Imperfektheitsgrad eine hinreichende Bedingung fu¨r
die Nichtexistenz von Bindingfunktionen her, siehe Sektion 2.3.
Additivit¨atderGraph-Entropie. Ko¨rner[56]fu¨hrtedieGraph-Entropie
( )X1 k k kH(G,p) = limsupmin log χ(G [U]) :U ⊆V(G ), p (x)> 1−ε2kk→∞
x∈U
als Gu¨temaß fu¨r ein Kodierungsproblemein, das sowohl vom GraphenG als
auch einer Wahrscheinlichkeitsverteilung p abha¨ngt. DieGraph-Entropieist
subadditivbezu¨glich der Vereinigung von Graphen auf der gleichen Knoten-
menge, insbesondere gilt fu¨r Komplementa¨rgraphen
H(p)≤H(G,p)+H(G,p) ∀p
wobei H(p) = H(K ,p) die sog. Shannon-Entropie (d.h. die Entropie dern
Wahrscheinlichkeitsverteilung p selbst) ist. Czisza´r et al. [31] zeigten, dass
letztere Ungleichung genau dann fu¨r alle Wahrscheinlichkeitsverteilungen p
mit Gleichheit erfu¨llt ist, wenn G perfekt ist.
Dies legt nahe, mithilfe des Wertes H(G,p)+H(G,p)−H(p) die Imper-
fektheit eines Graphen G auszudru¨cken. Es gilt
min{H(G,p)+H(G,p)−H(p) :p} = 0v
genau dann, wennG normal ist. Normale Graphen bilden eine bisher wenig
untersuchte Oberklasse perfekter Graphen. Ko¨rner und de Simone [59] ver-
muten,dassjederGraphnormalist, derwederC ,C nochC alsinduzierte5 7 7
Untergraphen entha¨lt (Normale-Graphen-Vermutung). Wir zeigen diese
Vermutung fu¨r einige erste Graphenklassen (Sektion 3.3) und geben ver-
schiedene Wege zur Konstruktion normaler Graphen an (Sektion 3.2). Da-
raus resultierende Konsequenzen zeigen leider, dass normale Graphen nicht
als‘fastperfekt’angesehen werdenk¨onnen,wiebishervermutet wurde(Sek-
tion 3.4). Insbesondere kann der Imperfektheitsgrad fu¨r normale Graphen
nicht beschra¨nkt werden. Da
max{H(G,p)+H(G,p)−H(p):p}= log imp(G)2
gilt, existieren also normale Graphen G, fu¨r welche die Differenz zwischen
max{H(G,p)+H(G,p)−H(p) : p} und min{H(G,p)+H(G,p)−H(p) : p}
beliebig groß ist. Damit ha¨ngt der Wert H(G,p)+H(G,p)−H(p) fu¨r nor-
male Graphen G stark von der Wahrscheinlichkeitsverteilung p ab, und wir
folgern, dass nicht normale Graphen, sondern solche mit kleinem Imperfekt-
heitsgrad in dieser Hinsicht ‘fast perfekt’ sind (siehe Sektion 3.4).
Das Stabile-Mengen-Polytop. Das Stabile-Mengen-Polytop STAB(G)
ist definiert als die konvexe Hu¨lle der Inzidenzvektoren aller stabilen Men-
gen von G; die Beschreibung durch facetten-definierende Ungleichungen
ist fu¨r die meisten Graphen unbekannt. Fu¨r alle Graphen bilden Nicht-
negativit¨atsbedingungen und Cliquebedingungen assoziiert mit maximalen
Cliquen Facetten von STAB(G), diese Facettentypen reichen jedoch nur
genaufu¨rperfekteGraphenaus[21,40,75]. Einenatu¨rlicheLP-Relaxierung
von STAB(G) ist daher das fraktionale Stabile-Mengen-Polytop  X|G|
QSTAB(G) = x∈R : x ≤ 1 ∀Q⊆G Cliquei+ 
i∈Q
und es gilt STAB(G)⊂ QSTAB(G) fu¨r alle imperfekten Graphen. Die Dif-
ferenzderbeidenPolytopeistalsoeinnatu¨rlichesMaßfu¨rdieImperfektheit.
Wir untersuchen dafu¨r
• die Facettenmenge von STAB(G) (hinsichtlich Anzahl und Art der
zusa¨tzlich beno¨tigten Facetten),
• den disjunktiven Index von QSTAB(G) (als die kleinste Anzahl von
Disjunktionen, um QSTAB(G) in ein ganzzahliges Polytop zu u¨ber-
fu¨hren, was dem Imperfektheitsindex imp (G) entspricht [1]),Ivi
• den Dilationsgrad von STAB(G) undQSTAB(G) (der nach Gerke und
McDiarmid [45] eine weitere Darstellung des Imperfektheitsgrades als
imp(G) = min{t : QSTAB(G)⊆t STAB(G)} liefert).
Wir geben verschiedene Resultate zu allen drei Konzepten an: wir be-
schreiben die Facetten der Stabile-Mengen-Polytope verschiedener Graphen
(Kapitel 4) und untersuchen sowohl Schranken fu¨r den Imperfektheitsgrad
als auch fu¨r den Imperfektheitsindex (Kapitel 5). Es zeigt sich, dass viele
Graphenklassen mit ‘einfach’ zu beschreibenden Stabile-Mengen-Polytopen
auch einen kleinen Imperfektheitsgrad aufweisen, wa¨hrend der Imperfekt-
heitsindex fu¨r fast alle untersuchten Graphenklassen unbeschra¨nkt ist. Wir
folgern, dass der Imperfektheitsgrad auch im polyedertheoretischen Sinne
ein sinnvolles Maß fu¨r die Imperfektheit darstellt.
Schlussfolgerung. Der Imperfektheitsgrad hat eine Verbindung zu allen
untersuchten Konzepten, da er
• sowohl in seiner urspru¨nglichen Definition als auch in Verbindung mit
Bindingfunktionen gute F¨arbungseigenschaften wiedergibt,
• eine obere Schranke fu¨r den Wert H(G,p)+H(G,p)−H(p)) liefert,
die unabh¨angig von der Wahrscheinlichkeitsverteilung p ist,
• der Dilationsgrad von STAB(G) und QSTAB(G) ist und Graphen
mit ‘einfach’ zu beschreibenden Stabile-Mengen-Polytopen auch einen
kleinen Imperfektheitsgrad aufweisen.
Damit ist der Imperfektheitsgrad mit allen untersuchten Konzepten kompa-
tibel und liefert ein geeignetes Maß fu¨r die Imperfektheit eines Graphen, da
Graphen mit kleinem Imperfektheitsgrad tatsa¨chlich hinsichtlich mehrerer
Eigenschaften als ‘fast perfekt’ angesehen werden k¨onnen.Acknowledgments
I am greatfully indebted to many peoplewhosupportedmy workduringthe
last years.
First of all, I thank Martin Gro¨tschel and Robert Weismantel who gave
me the opportunity to work in their groups, who constantly supported and
encouraged my research, and who shared with me their knowledge on many
challenging topics in combinatorial optimization.
I also thank Thomas Liebling for his constant interest in my work, as a
member of the advisory board of the Zuse Institute Berlin (ZIB), and as a
refereeoftheresearchgroup“Algorithms, Structure,Randomness”inBerlin
(ASZ). My work was partially supported by this research group, funded by
the Deutsche Forschungsgemeinschaft (DFG), grant FOR 413.
My particular thanks go to Arnaud Pˆecher, my main coauthor, for a
continuously fruitful joint