ISBN 9783843953153

978-3-8439-5315-3, Reihe Mathematik

Oliver Bachtler
On Algorithmic Certification of Graph Structures

201 Seiten, Dissertation Technische Universität Kaiserslautern (2023), Hardcover, A5

Zusammenfassung / Abstract

Many open problems in graph theory aim to verify that a specific class of graphs has a certain property. One example, which we study extensively in this thesis, is the 3-decomposition conjecture. It states that every cubic graph can be decomposed into a spanning tree, cycles, and a matching. Our most noteworthy contributions to this conjecture are a proof that graphs which are star-like satisfy the conjecture and that several small graphs, which we call forbidden subgraphs, cannot be part of minimal counterexamples. Moreover, we use these forbidden subgraphs to deduce that 3-connected cubic graphs of path-width at most 4 satisfy the 3-decomposition conjecture.

In the second part of this thesis, we delve deeper into two steps of the proof for path-width 4 graphs. We show how to formalise the techniques used in such a way that they can be implemented and solved algorithmically. As a result, only the work that is "interesting" to do remains. While one step is specific to the 3-decomposition conjecture, we derive a general algorithm for the other. This algorithm takes a class of graphs G as an input, together with a set of graphs U, and a path-width bound k. It then attempts to answer the following question: does any graph in G that has path-width at most k contain a subgraph in U? We show that this problem is undecidable in general, so our algorithm does not always terminate, but we also provide a general criterion that guarantees termination.

In the final part of this thesis we investigate two connectivity problems on directed graphs. We prove that verifying the existence of an st-path in a local certification setting, cannot be achieved with a constant number of bits. Furthermore, we investigate the complexity of the separating by forbidden pairs problem, which asks for the smallest number of arc pairs that are needed such that any st-path completely contains at least one such pair. We show that the corresponding decision problem in SigmaTwoP-complete.