|
Extremal colorings and extremal satisfiability
Zumstein, Philipp
|
DOI:
|
https://doi.org/10.3929/ethz-a-005951186
|
|
URL:
|
https://madoc.bib.uni-mannheim.de/34171
|
|
Weitere URL:
|
https://www.research-collection.ethz.ch/handle/20....
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-341712
|
|
Dokumenttyp:
|
Dissertation
|
|
Erscheinungsjahr:
|
2009
|
|
Ort der Veröffentlichung:
|
Zürich
|
|
Verlag:
|
Univ.
|
|
Hochschule:
|
ETH Zürich
|
|
Gutachter:
|
Welzl, Emo
|
|
Datum der mündl. Prüfung:
|
15 September 2009
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Zentrale Einrichtungen > UB Universitätsbibliothek
|
|
Fachgebiet:
|
004 Informatik
510 Mathematik
|
|
Fachklassifikation:
|
MSC:
|
|
Normierte Schlagwörter (SWD):
|
Graphfärbung , Ramsey-Theorie , Erfüllbarkeitsproblem , Extremalproblem
|
|
Freie Schlagwörter (Englisch):
|
graph coloring , ramsey theory , satisfiability of boolean formulas , extremal combinatorics
|
|
Abstract:
|
Combinatorial problems are often easy to state and hard to solve. A whole bunch of graph coloring problems falls into this class as well as the satisfiability problem. The classical coloring problems consider colorings of objects such that two objects which are in a relation receive different colors, e.g., proper vertex-colorings, proper edge-colorings, or proper face-colorings of plane graphs.
A generalization is to color the objects such that some predefined patterns are not monochromatic. Ramsey theory deals with questions under what conditions such colorings can occur. A more restrictive version of colorings forces some substructures to be polychromatic, i.e., to receive all colors used in the coloring at least once. Also a true-false-assignment to the boolean variables of a formula can be seen as a 2-coloring of the literals where there are restrictions that complementary literals receive different colors.
Mostly, the hardness of such problems is been made explicit by proving that they are NP-hard. This indicates that there might be no simple characterization of all solvable instances. Extremal questions then become quite handy, because they do not aim at a complete characteriziation, but rather focus on one parameter and ask for its minimum or maximum value.
The goal of this thesis is to demonstrate this general way on different problems in the area of graph colorings and satisfiability of boolean formulas.
First, we consider graphs where all edge-2-colorings contain a monochromatic copy of some fixed graph H. Such graphs are called H-Ramsey graphs and we concentrate on their minimum degree. Its minimization is the question we are going to answer for H being a biregular bipartite graph, a forest, or a bipartite graph where the size of both partite sets are equal.
Second, vertex-colorings of plane multigraphs are studied such that each face is polychromatic. A natural parameter to upper bound the number of colors which can be used in such a coloring is the size g of the smallest face. We show that every graph can be polychromatically colored with $\floor{3g-5}{4}$ colors and there are examples for which this bound is almost tight.
Third, we consider a variant of the satisfiability problem where only some (not necessarily all) assignments are allowed. A natural way to choose such a set of allowed assignments is to use a context-free language. If in addition the number of all allowed assignments of length n is lower bounded by $\Omega(\alpha^n)$ (an) for some $\alpha > 1$, then this restricted satisfiability problem will be shown to be NP-hard. Otherwise, there are only polynomially many allowed assignments and the restricted satisfiability problem is proven to be polynomially solvable.
|
|
Übersetzung des Abstracts:
|
Kombinatorische Probleme sind oft einfach zu formulieren aber schwierig zu lösen. Eine ganze Reihe von Graphenfärbungs-Problemen fällt in diese Klasse wie auch das Erfüllbarkeitsproblem von boolschen Formeln. Klassische Färbungsprobleme betrachten Färbungen von Objekten, so dass je zwei Objekte, die in einer Relation stehen, verschiedene Farben erhalten, z.B., gültige Knotenfärbungen, gültige Kantenfärbungen oder gültige Färbungen der Gebiete eines planaren Graphen.
Eine Verallgemeinerung sind Färbungen, so dass vordefinierte Muster nicht einfarbig sind. Die Ramsey-Theorie behandelt Fragestellungen, wann solche Färbungen vorkommen können. Eine eingeschränktere Variante von Färbungen zwingt gewisse Teilstrukturen polychromatisch zu sein, d.h., alle Farben kommen mindestens einmal vor. Ebenso kann eine Belegung der boolschen Variablen einer Formel mit Wahr- und Falsch-Werten als eine 2-Färbung der Literale angesehen werden, wobei komplementäre Literale unterschiedliche Farben erhalten.
Die Schwere von solchen Problemen wird meistens dadurch gezeigt, dass man beweist, dass sie NP-schwer sind. Dies deutet darauf hin, dass es keine einfache Charakterisierung aller lösbaren Instanzen geben wird. Extremale Fragestellungen sind dann recht nützlich, da sie nicht eine vollständige Charakterisierung erzielen wollen, sondern einen Parameter fixieren und nach dessen Minimum
oder Maximum fragen.
Das Ziel dieser Doktorarbeit ist es diesen allgemeinen Weg anhand verschiedenener Probleme der Graphenfärbbarkeit und
Erfüllbarkeit von logischen Formeln aufzuzeigen.
Zuerst betrachten wir Graphen, in welchen jede Kanten-2-Färbung eine monochromatische Kopie eines bestimmten Graphen H enthält. Solche Graphen nennt man H-Ramsey Graphen und wir konzentrieren uns auf deren minimalen Knotengrad. Die Frage nach dessen Minimierung beantworten wir für bireguläre bipartite Graphen,Wälder und bipartite Graphen mit gleich grossen Partitionsklassen.
Als Zweites untersuchen wir Knotenfärbungen von planaren Multigraphen, so dass der Rand jedes Gebietes polychromatisch gefärbt ist. Ein natürlicher Parameter, um die Anzahl Farben nach oben zu beschränken, ist die Grösse g des kleinsten Gebietes. Wir zeigen, dass jeder planare Multigraph mit $\lceil\frac{3g-5}{4}\rceil$ Farben polychromatisch gefärbt werden kann, und es gibt Beispiele, die zeigen, dass diese Schranke fast scharf ist.
Drittens betrachten wir eine Variante des Erfüllbarkeitsproblems, wobei nur eine Teilmenge aller Belegungen (nicht unbedingt alle) erlaubt sind. Eine natürliche Weise, um solch eine Teilmenge von Belegungen zu wählen, ist eine kontextfreie Grammatik. Falls zusätzlich die Anzahl von erlaubten Belegungen der Länge $n$ von unten durch $\Omega(\alpha^n)$ abgeschätzt werden kann für ein $\alpha > 1$, dann wird das eingeschränkte Erfüllbarkeitsproblem wiederum NP-schwer sein. Andernfalls sind nur polynomiell viele Belegungen erlaubt und es wird gezeigt, dass das eingeschränkte Erfüllbarkeitsproblem polynomiell lösbar ist.
(Deutsch)
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 | Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)
