Matchings in balanced hypergraphs [Elektronische Ressource] / Robert Berthold Scheidweiler

Description

Matchings in balanced hypergraphsVon der Fakultat¨ fur¨ Mathematik, Informatik und Naturwissenschaften der RWTH AachenUniversity zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaftengenehmigte Dissertationvorgelegt vonDiplom-MathematikerRobert Berthold ScheidweilerausDuren-Birk¨ esdorf.Berichter: Universitatsprofessor¨ Dr. Eberhard TrieschUniversit¨ Dr. Arie M.C.A. KosterTag der mundlichen¨ Prufung:¨ 19. April 2011Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfugbar¨ .DanksagungIn den letzten funf¨ Jahren habe ich am Lehrstuhl II fur¨ Mathematik der RWTH Aachen Uni-versity die vorliegende Dissertation verfasst. Einigen gebuhrt¨ fur¨ ihre Unterstutzung¨ undHilfe wahrend¨ dieser Zeit besonderer Dank. Zuallererst mochte¨ ich mich bei dem Betreuermeiner Dissertation und meinem Chef, Eberhard Triesch, bedanken. Durch ihn habe ich dasThema dieser Arbeit erhalten, das mir sehr ans Herz gewachsen ist. Er hat mir bei meinenForschungen immer mit Rat und Tat zur Seite gestanden und mich auch bei langer¨ andauern-den Durststrecken niemals unter Druck gesetzt. Seine positive Unterstutzung¨ und geduldigeHilfe haben mich motiviert, diese Arbeit zu vollenden. Weiterhin mochte¨ ich mich bei ArieKoster, meinem Zweitgutachter, bedanken. Mehrfach hat er im Verlauf meiner PromotionAnregungen gegeben, die dann in die Dissertation eingeflossen sind.

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2011
• Nombre de lectures: 14
• Langue: Deutsch

Extrait

Matchings in balanced hypergraphs

VonderFakult ¨ atf ¨ urMathematik,InformatikundNaturwissenschaftenderRWTHAachen University zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften genehmigte Dissertation

vorgelegt von Diplom-Mathematiker Robert Berthold Scheidweiler aus D ¨ uren-Birkesdorf.

Berichter:Universit ¨ atsprofessorDr.EberhardTriesch Universit¨tsprofessor Dr. Arie M.C.A. Koster a

Tagderm ¨ undlichenPru ¨ fung:19.April2011 Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfu¨  gbar.

Danksagung

Indenletztenf ¨ unfJahrenhabeichamLehrstuhlIIf ¨ urMathematikderRWTHAachenUni- versitydievorliegendeDissertationverfasst.Einigengebu ¨ hrtf ¨ urihreUnterst ¨ utzungund Hilfe wa¨hrend dieser Zeit besonderer Dank.  Zuallererst  mo¨  chte ich mich bei dem Betreuer meiner Dissertation und meinem Chef, Eberhard Triesch, bedanken. Durch ihn habe ich das Thema dieser Arbeit erhalten, das mir sehr ans Herz gewachsen ist. Er hat mir bei meinen ForschungenimmermitRatundTatzurSeitegestandenundmichauchbeil ¨ angerandauern- denDurststreckenniemalsunterDruckgesetzt.SeinepositiveUnterst¨utzungundgeduldige Hilfehabenmichmotiviert,dieseArbeitzuvollenden.Weiterhinm ¨ ochteichmichbeiArie Koster, meinem Zweitgutachter, bedanken. Mehrfach hat er im Verlauf meiner Promotion Anregungen gegeben, die dann in die Dissertation eingeflossen sind. Vor der endgu¨  ltigen Ab- gabehaterdurchseineVerbesserungsvorschl¨age,f¨urdieichsehrdankbarbin,zurjetzigen FormderArbeitbeigetragen.Dankenm ¨ ochteichaußerdemBertRanderath,dermirhalf, einige Startschwierigkeiten zu u¨  berwinden, als ich begann, die balancierten Hypergraphen zu erforschen. Hartmut  Fu¨  hr hat sehr viel Zeit darauf verwendet, mir die harmonische Analysis na ¨ herzubringen.SeineBem ¨ uhungenhabenmeinePromotionweitervorangebracht.Bei meinenKollegenm¨ochteichmichfu¨rdiegroßartigeArbeitsatmospha¨reamLehrstuhlundfu¨r ihre Hilfsbereitschaft bedanken.

3

Preface

The present work deals with the matching and vertex cover problem in balanced hypergraphs. This class of hypergraphs is, according to the definition by Berge in the 70s, one possible gen- eralization of bipartite graphs. Several authors have investigated the matching problem in this class so far (cf. [FHO74], [CC87], [CCKV96], [HT02] and [CSZ07]). On the one hand there are linear programming algorithms, which find maximum matchings and minimum vertex cov- ers in balanced hypergraphs, due to the integrality of associated polytopes. On the other hand no polynomial matching algorithm is known, which makes use of the special combinatorial properties of this class of hypergraphs, e.g. its strong coloring properties. In our opinion this is the main reason for investigating the matching problem in balanced hypergraphs. Hence, the foremost aim of this work is to provide better insight into matching and vertex cover problems for balanced hypergraphs. In the first chapter we define basic notions about graphs, hypergraphs, matchings, vertex cov- ers and colorings. Most of the definitions are widely-used and can be found, for instance, in [Ber89]. The next chapter deals with the class of balanced hypergraphs. At first, we briefly discuss the matching problem in two special subclasses, namely balanced hypergraphs with maximum degree two and totally balanced hypergraphs. After that we discuss hereditary and coloring properties of balanced hypergraphs, drawing completely from Berge, cf. [Ber70] and [Ber73]. Then we present an algorithm developed by Cameron and Edmonds [CE90] for vertex 2- coloring in balanced hypergraphs and subsequently, following one of Berge’s ideas, we pro- pose an algorithm fork-coloring the vertex set of a balanced hypergraph. our knowledge, To thekbut has never been described completely in the literature-coloring algorithm is known before. Moreover, we analyse the connection between regularity and maximum matchings in balanced hypergraphs. It is generally known that the edge set of a regular balanced hy- pergraph decomposes into perfect matchings. We give strong estimations for the matching number, under the condition that a balanced hypergraph does not differ much from regularity. Furthermore, we obtain that our estimations are not improvable and that a matching, having at least the size of our estimations, can be found with the above mentioned coloring algorithms appliedtothedualhypergraph.ThenwepresentK ˝ onig’stheoremforbalancedhypergraphs. It was first proved in [BV70] and [FHO74]. We give a new inductive and combinatorial proof ofK ˝ onig’stheorembasedonourcoloringandregularityconsiderations.Next,weexamine further duality properties between matchings and vertex covers and give several new results, which can be interpreted as combinatorial formulations and strengthenings of the complemen- tary slackness relation. However, we emphasize that we do not use any linear programming arguments here. In the following we investigate polyhedra, which are associated to match-

5

ing and covering problems in balanced hypergraphs. We give a short combinatorial proof of their integrality, which is due to Lova´sz (cf. [Lov72]). The proof, which is commonly cited in literature, can be found in [FHO74]. In the rest of the second chapter we outline how our new ideas can be used to augment matchings in algorithms. Moreover we model matching problems as Leontief Flows. The ideas of chapter two are transferred to the dual hypergraph, from which we obtain results about stable sets and edge covers. The third chapter is concerned with a new decomposition theory for balanced hypergraphs. Based on Ko˝ nig’s theorem and the considerations of the preceding chapter, we generalize the Gallai-Edmonds decomposition for graphs, cf. [Gal65] and [Edm68], to the class of balanced hypergraphs in four different ways. In contrast to the classical decomposition we do not only decompose the vertex set, we also decompose the edge set of our hypergraphs. Our first de- composition theorem considers weighted matchings and we give an algorithm to achieve this decomposition. As a special case of the weighted matching decomposition we consider max- imum matchings, regarding the number of contained edges. Furthermore, we compare our decomposition to the classical one. In the next decomposition theorem we investigate max- imum matchings, regarding the number of covered vertices. We prefer a slightly different decomposition here, due to the special weight function. As a last step we apply our decompo- sition to the dual hypergraph and obtain results about stable sets and edge covers. In chapter four we prove Hall’s theorem for balanced hypergraphs. Hall’s theorem has been proved at first by Conforti et. al. ( [CCKV96]). Huck and Triesch [HT02] stated the first com- binatorial proof. Now, we give a new, short, and combinatorial proof of Hall’s theorem based on our decomposition theory and the regularity considerations of chapter two. Additionally, we investigate the connection between the Hall condition and vertex covers. The first topic of chapter five is the class of extendable and balanced hypergraphs. A hyper- graph is called extendable, a notion of Plummer [Plu80], if any of its edges is contained in a perfect matching. We provide several strong characterizations of such hypergraphs. In a second step we offer more than 20 new characterizations of the whole class of balanced hy- pergraphs. Then we discuss briefly, which parts of our matching theory can be conveyed to the bigger class of normal hypergraphs defined by Lova´sz in [Lov72]. The last part of chapter five deals with several interesting subclasses of balanced hypergraphs, for example the factor critical ones and some hypergraphs having special degree properties. The chapter’s last result establishes a connection between Hall’s theorem and the regularity considerations of chapter two. By means of Hall’s theorem we are able to achieve a new regularity result, which gener- alizes an old theorem of Ore [Ore62] for bipartite graphs to the class of balanced hypergraphs. In the final chapter we pose open questions and possible areas for future research based on this work. A small part of our decomposition theory and our new proof of Ko˝ nig’s theorem can also be found in a preprint on arXiv.org [ST09].

6

Contents

Contents 1 Definitions and Notations 1.1 Hypergraphs and Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Matchings and Vertex Covers . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Balanced hypergraphs 2.1 The special caseΔ(H) =2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The special case of totally balanced hypergraphs . . . . . . . . . . . . . . . . 2.3 Colorings of balanced hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 2.4 Matchings and vertex covers of balanced hypergraphs . . . . . . . . . . . . . 2.5 Integral polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Algorithmic aspects of matchings and vertex covers . . . . . . . . . . . . . . 2.7 Modelling of matching problems as Leontief Flow Problem . . . . . . . . . . 3 Decomposition theorems 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Construction Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 The special case ofE . . . . . . . . . . . . . . . . .-maximum matchings . 3.5 Comparison with the classical decomposition I . . . . . . . . . . . . . . . . 3.6 The case ofV-maximum matchings . . . . . . . . . . . . . . . . . . . . . . 3.7 Comparison with the classical decomposition II . . . . . . . . . . . . . . . . 3.8 Decomposition for stable sets and edge covers . . . . . . . . . . . . . . . . . 4 Hall’s theorem 5 Applications 5.1 Extendability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Characterizations of balanced hypergraphs . . . . . . . . . . . . . . . . . . . 5.3 Matchings in normal hypergraphs . . . . . . . . . . . . . . . . . . . . . . . 5.4 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Open problems and future work Bibliography Index Index of Symbols

7 9 9 11 12 13 14 16 16 19 31 32 33 35 35 36 39 40 42 43 46 47 49 53 53 55 57 59 63 65 69 71