Extremal colorings and extremal satisfiability


Zumstein, Philipp


[img]
Preview
PDF
eth-564-02.pdf - Published

Download (950kB)

DOI: https://doi.org/10.3929/ethz-a-005951186
URL: https://madoc.bib.uni-mannheim.de/34171
Additional URL: https://www.research-collection.ethz.ch/handle/20....
URN: urn:nbn:de:bsz:180-madoc-341712
Document Type: Doctoral dissertation
Year of publication: 2009
Place of publication: Zürich
Publishing house: Univ.
University: ETH Zürich
Evaluator: Welzl, Emo
Date of oral examination: 15 September 2009
Publication language: English
Institution: Zentrale Einrichtungen > University Library
Subject: 004 Computer science, internet
510 Mathematics
Classification: MSC:
Subject headings (SWD): Graphfärbung , Ramsey-Theorie , Erfüllbarkeitsproblem , Extremalproblem
Keywords (English): 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.
Translation of the abstract: 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. (German)




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.




Metadata export


Citation


+ Search Authors in

BASE: Zumstein, Philipp

Google Scholar: Zumstein, Philipp

ORCID: Zumstein, Philipp ORCID: 0000-0002-6485-9434

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item