Varianten zur Matching Extendability in Graphen

Schmidt, Isabelle Gertrud; Koster, Arie Marinus; Triesch, Eberhard

doi:38136

Varianten zur Matching Extendability in Graphen = Some generalizations of matching extendability in graphs

Schmidt, Isabelle Gertrud^RWTH*

2019

Verantwortlichkeitsangabevorgelegt von Diplom-Mathematikerin Isabelle Gertrud Schmidt

ImpressumAachen 2019

Umfang1 Online-Ressource (iv, 114 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2019

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2019-04-26

Online
DOI: 10.18154/RWTH-2019-04138
URL: https://publications.rwth-aachen.de/record/760372/files/760372.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
2-matching extendability (frei) ; b-matching extendability (frei) ; matching extensions (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Ein 1-Matching (oder einfach Matching) in einem Graph G=(V,E) kann einerseits als eine Menge unabhängiger, d.h. paarweise nicht inzidenter, Kanten definiert werden. Andererseits kann ein 1-Matching als eine Kantenfunktion beschrieben werden, die jeder Kante den Wert 0 oder 1 zuordnet unter Berücksichtigung, dass die Summe der Werte inzidenter Kanten zu einer Ecke maximal 1 sein darf. Ein 1-Matching heißt perfekt, falls die Summe der Werte inzidenter Kanten in jeder Ecke gleich 1 ist. Mit der Größe eines Matchings bezeichnen wir die Summe der Werte der Kanten des Matchings. Ist es in einem Graph G möglich, jedes 1-Matching der Größe k zu einem perfekten 1-Matching zu erweitern, so nennen wir G 1-Matching k-extendable. Für einen gegebenen Graph G bezeichnet die Extendabilityzahl von G die größte Zahl k mit der Eigenschaft, dass G 1-Matching k-extendable ist. Die Beschreibung des 1-Matchings als Kantenfunktion lässt sich zu dem allgemeinen Konzept der b-Matchings erweitern. In Analogie zu der 1-Matching Extendability definieren wir die b-Matching Extendability sowie als Spezialfall die 2-Matching Extendability. Der Schwerpunkt dieser Arbeit liegt auf den Untersuchungen zur Komplexität des Problems der Bestimmung der Extendabilityzahl für 2-Matchings und b-Matchings. Diese Probleme bezeichnen wir als 2-Matching bzw. b-Matching Extendabilityproblem. Auf Grundlage eines Überblicks über die Theorie der Extendability für 1-Matchings stellen wir ein Ergebnis von Hackfeld aus dem Jahr 2013 vor, das die co-NP-Vollständigkeit des 1-Matching Extendabilityproblems für allgemeine Graphen zeigt. Weiter diskutieren wir ausführlich ein Ergebnis von Zhang und Zhang aus dem Jahr 2006, das beweist, dass das 1-Matching Extendabilityproblem für bipartite Graphen in polynomieller Zeit lösbar ist. Diese beiden Ergebnisse verallgemeinern wir im folgenden für 2- und b-Matchings. Da bei der Betrachtung des Begriffs der Extendability auf 2-Matchings verschiedene Ansätze sinnvoll erscheinen, führen wir zunächst die Konzepte der simple, Typ A und Typ B 2-Matching k-Extendability ein. Auf diese Konzepte übertragen wir eine der grundlegenden Eigenschaften der 1-Matching Extendability; diese besagt, dass ein Graph, der k-extendable ist auch (k-1)-extendable ist. Anschließend können wir für alle Konzepte die co-NP-Vollständigkeit des 2-Matching Extendabilityproblems für allgemeine Graphen auf der Grundlage von Hackfeld nachweisen. Für den Typ B können wir zusätzlich die co-NP-Vollständigkeit aus den nachfolgenden Ergebnissen bezüglich der b-Matchings folgern. Anschließend untersuchen wir die in den vorherigen Kapiteln betrachteten Ergebnisse für b-Matchings im Sinne des Typs B auf allgemeinen und bipartiten Graphen. Dabei stellen wir einen alternativen Algorithmus zur Bestimmung der b-Matching k-Extendability für bipartite Graphen vor, der das Ergebnis von Zhang und Zhang für bipartite Graphen bezüglich 1-Matchings verallgemeinert.

On the one hand a 1-matching or simply a matching of a graph G=(V,E) is a set of pairwise non incident edges. On the other hand it can be described as an edge function which maps the values 0 and 1 to the edges of G such that the sum of values of incident edges to each vertex is at most 1. A 1-matching is called perfect if the sum of incident edges in each vertex equals 1. We define the size of a 1-matching as the sum of values over all edgesWe say that a graph G is 1-matching k-extendable if every matching of size k in G extends to a perfect matching of G. The extendability number of G is the maximal integer k such that G is 1-matching k-extendable. Describing a 1-matching as an edge function yields to the more general concept of b-matchings. In analogy to the 1-matching extendability we define the b-matching extendability and the 2-matching extendability as a special case. In this thesis we study the complexity of determining the extendability number for 2- and b-matchings. After a brief survey of the theory on 1-matching extendability we present a result of hackfeld from 2013. He proved that the extendability problem is co-NP-complete for general graphs. Furthermore, we discuss a result of Zhang und Zhang showing that there is a polynomial time algorithm which computes the 1-matching extendability number of bipartite graphs. We generalize both results for 2-and b-matchings. Considering the extendability for 2-Matchings it points out that different approaches seem to be natural. Thus we introduce the concepts of simple, Typ A and Typ B 2-matching k-extendability. For these concepts we transfer a basic property of 1-matching k-extendable graphs. In particular, we show that a graph which is simple (resp. Typ A or Typ B) k-extendable is simple (resp. Typ A or Typ B) (k-1)-extendable. Moreover, we prove that for general graphs the problem of determining the simple, Typ A and Typ B 2-matching extendability number is co-NP-complete by using an analog deduction to the proof of Hackfelds result. For the Typ B 2-matching extendability we obtain the same statement from the following result on the b-matching extendability. In particular, we generalize all results of Typ B for general and bipartite graphs to the b-matching extendability. We give an (alternative) algorithm which determines the b-matching extendability number for bipartite graphs. This procedure generalizes the result of Zhang und Zhang for the 1-matching extendability number of bipartite graphs.

OpenAccess:
PDF
(additional files)