Varianten zur Matching Extendability in Graphen

• Some generalizations of matching extendability in graphs

Schmidt, Isabelle Gertrud; Triesch, Eberhard (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen (2019)
Doktorarbeit

Dissertation, RWTH Aachen University, 2019

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.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl II für Mathematik (für Ingenieure) [113210]