title: Perfect pseudo matchings on snarks
Creators: name: Schwendinger, Benjamin
Publisher: name: TU Wien
Year: 2019
Subjects: subject: Graphenalgorithmen
subject: Snarks
subject: Pseudo Matchings
subject: graph algorithms
subject: snarks
subject: pseudo matchings

description: Das Problem des Cycle Double Cover (CDC) wird nun seit über 45 Jahren von Graphentheoretikern betrachtet. Obwohl dieses Problem für viele Familien von Graphen bereits gelöst werden konnte, bleibt es für den allgemeinen Fall weiterhin ungelöst ([31]). Die Aufgabenstellung ist simpel: Gegeben sei ein brückenloser Graph G. Gibt es eine Familie von Zyklen, bestehend aus Kanten von G, sodass jede Kante von G von dieser Familie genau doppelt überdeckt wird? In dieser Diplomarbeit versuchen wir einen neuen, bisher nicht untersuchten Lösungsansatz für das CDC zu entwickeln. Dabei greifen wir auf das exakte Verfahren der ganzzahligen linearen Programmierung zurück. Wir beginnen zuerst mit dem Begriff des Pseudo Matchings. Dieses stellt eine Generaliserung des graphentheoretischen Matchings dar. Analog zu gewöhnlichen Matchings definieren wir weiters den Begriff des perfect pseudo matching (PPM). In weiterer Folge betrachten wir den Kontraktionsgaphen, der durch die Kontraktion eines Graphen mit einem zugehörigen PPM entsteht. Sollte der Kontraktionsgraph planar bzw. zumindest ohne K_5-Minor sein, so beweisen wir fußfassend auf der Vorarbeit von Fan und Zhang ([11]), dass der ursprüngliche Graph dann ein CDC besitzen muss. Für planare Graphen wurde dies bereits durch Fleischner bewiesen ([13]). Nachdem Jaeger ([21]) bewies, dass ein Gegenbeispiel mit minimaler Kantenanzahl für das CDC ein Snark (ein zyklisch 4-Kanten zusammenhängender, brückenloser kubischer Graph mit chromatischem Index 4) sein muss, betrachten wir in Folge Snarks bis zu einer Ordnung von 52 Knoten. Dabei können wir einerseits das CDC für Graphen bis zu einer Knotenanzahl von 26 verifizieren, anderseits werden auch die Limitationen unseres neuen Ansatzes aufgezeigt. So finden wir Snarks mit 26 (bzw. 28) Knoten, die kein planares (bzw. K_5-Minor freies) PPM besitzen und für welche sich somit mittels unseres entwickelten Ansatzes keine Aussage treffen lässt, ob sie ein CDC besitzen. Um die Effizienz unseres entwickelten Ansatzes und des dahinter liegenden Algorithmus aufzuzeigen, werden zuletzt auch weitere zufällige kubische Graphen bis zu einem Knotengrad von 100 betrachtet.
description: The graph theoretic problem of the Cycle Double Cover (CDC) has been around for over 45 years. It still remains to be an open problem, although specilizations for many families of graphs have been proven in this time period ([31]). The question is easy to state: Given a bridgeless graph G, does a collection of cycles of G exist, such that every edge of G appears in exactly two of these cycles? In this thesis we try to develop a new approach for the CDC, which has not been investigated so far. There we will make use of integer linear programming as exact solution method. First, we start with the definition of a pseudo matching which is a generalization of the graph theoretic matching. Analogous to matchings we further define the term of a perfect pseudo matching (PPM). We continue with the examination of the contraction graph, which arises through the contraction of a graph and an according PPM of this graph. If the contraction graph is planar (or at least has no K_5-minor) then we will prove, based on the work of Fan and Zhang ([11]), that the original graph has to have a CDC. Fleischner proved this for planar graphs ([13]). Since Jaeger proved in ([21]) that a counterexample with a minimum number of edges to the CDC has to be a snark (a cyclically 4-edge connected, bridgeless, cubic graph with edge chromatic number 4), we will further examine snarks up to an order of 52 vertices. There we can verify the CDC for graphs up to a size of 26 vertices, but our experiments also show the limitations of our new developed approach. So we will find snarks with 26 (resp. 28) vertices for which no planarizing (resp. K_5-minor free) PPM exists and therefore our approach cannot decide, whether there exists a CDC for them or not. Last but not least to demonstrate the efficient running time of our approach we will test it with cubic random graphs with up to 100 vertices.