[Back]


Doctor's Theses (authored and supervised):

B. Klocker:
"Combinatorial Optimization Approaches for Graph Construction Problems";
Supervisor, Reviewer: G. Raidl, H. Fleischner; Institute of Logic and Computation, 2020; oral examination: 2020-03-25.



English abstract:
Many open problems in the field of graph theory are concerned with the existence or non-existence of graphs with certain properties. In this thesis we consider three such graph theoretic problems and develop algorithms to search for graphs with the wanted properties. Although we cannot use computer search to prove the non-existence of a graph with certain properties within a usually infinite set of graphs, we can apply our algorithms to prove the non-existence for all graphs up to a certain size. For some (sub-)problems we focus on developing a practically effective algorithm that only checks if a given graph satisfies certain properties. This can then be combined with an enumeration and filtering approach to search for such graphs. As tool set for our algorithms we use various techniques from the field of combinatorial optimization. Strictly speaking the problem of searching for a graph with certain properties is not an optimization problem, but many graph properties are defined via substructures that minimize or maximize an objective.The first problem we consider is about the existence of uniquely hamiltonian planar graphs with minimum degree three. A prominent conjecture of Bondy and Jackson states that such graphs do not exist. To search for such graphs we consider two different kinds of approaches. The first approach tries to find uniquely hamiltonian graphs with minimum degree three and an embedding minimizing the number of crossings and the number of degree two vertices. We formalize an optimization problem for this purpose and propose a general variable neighborhood search (GVNS) for solving it heuristically. The different types of used neighborhoods also include an exponentially large neighborhood that is effectively searched by means of branch-and-bound. To check feasibility of neighbors we need to solve hamiltonian cycle problems, which is done in a delayed manner to minimize the computational effort. We compare three different configurations of the GVNS. Although our implementation could not find a uniquely hamiltonian planar graph with minimum degree three disproving Bondy and Jackson's conjecture, we were able to find uniquely hamiltonian graphs with one vertex of degree two and crossing number four for all graph orders from 10 to 100. In a second approach we are searching for planar graphs with minimum degree three that contain a stable fixed edge cycle (SFE-cycle) or equivalently a stable cycle with one vertex of degree two. We show that such a graph can be used to construct a uniquely hamiltonian planar graph with minimum degree three. For generating candidate graphs we use the program plantri and for checking if they contain an SFE-cycle we propose three approaches. Two of them are based on integer linear programming (ILP) and the other is a cycle enumeration algorithm. To reduce the search space we prove several properties a minimum planar graph with minimum degree three containing an SFE-cycle must satisfy, the most significant being triangle freeness. Comparing the three algorithms shows that the enumeration is more effective on small graphs while for larger graphs the ILP-based approaches perform better. Finally, we use the enumeration approach together with plantri to prove that there does not exist a planar graph with minimum degree three that contains an SFE-cycle with 24 or fewer vertices. This verifies Bondy and Jackson's conjecture for all graphs with up to 25 vertices.In the second part of this thesis we formulate an algorithm for finding smooth graphs, a special subclass of hamiltonian 4-regular graphs, with small independence numbers. To this end we formalize a family of satisfaction problems and propose a branch-and-bound based approach for solving them. Strong bounds are obtained by exploiting graph-theoretic aspects including new results obtained in cooperation with leading graph theorists. Based on a partial solution we derive a lower bound by computing an independent set on a partial graph and finding a lower bound on the size of possible extensions. The algorithm is used to test conjectured lower bounds on the independence numbers of smooth graphs and some subclasses of smooth graphs. In particular for the whole class of smooth graphs we test the lower bound of 2n/7 for all smooth graphs with at least n 12 vertices and can prove the correctness for all 12 n 24. Furthermore, we apply the algorithm on different subclasses, such as all triangle free smooth graphs.Finally, in the third part we are considering an extension of the minor concept to transitioned graphs, which arise in the context of the cycle double cover conjecture. This famous conjecture is strongly related to the compatible circuit decomposition (CCD) problem. A recent result by Fleischner et al. (2018) gives a sufficient condition for the existence of a CCD in a transitioned 2-connected eulerian graph, which is based on an extension of the definition of K5-minors to transitioned graphs. Graphs satisfying this condition are called sup-undecomposable K5 (SUD-K5)-minor-free graphs. We formulate a generalization of this property by replacing the K5 by a 4-regular transitioned graph H, which is part of the input. Furthermore, we consider the decision problem of checking for two given graphs if the extended property holds. We prove that this problem is NP-complete but can be solved in polynomial time if the size of H is fixed. We then formulate an equivalent problem, present a mathematical model for it, and prove its correctness. This mathematical model is then translated into a mixed integer linear program (MILP) and a boolean satisfiability problem (SAT) for solving it in practice. Non-trivial symmetry breaking constraints are proposed, which improve the solving times of both models considerably. Compared to the MILP model the SAT approach performs significantly better. We used the faster SAT approach to further test graphs of graph theoretic interest and were able to get new insights. Among other results we found snarks with 30 and 32 vertices that do not contain perfect pseudo-matchings, that are spanning subgraphs consisting of K2 and K1,3 components whose contraction lead to SUD-K5-minor-free graphs.


Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_292113.pdf


Created from the Publication Database of the Vienna University of Technology.