Optimal Graph Coverings with Connected Subgraphs

Abstract

Graph covering problems are among the most classical and central subjects in graph theory and play a huge role in many mathematical models for various real-world applications. The fundamental distinction in graph covering is between covering the edges or, respectively, the vertices of a graph. The edge covering problem belongs to the graph theory community and the contributions often comprise theoretical bounds or (in)approximability results. Vertex covering problems, on the other hand, are mostly motivated by applications and most contributions contain heuristic or approximation algorithms, integer programming formulations, or polyhedral studies to strengthen the respective linear programming relaxations. The thesis reviews both fields and gives a categorization and overview of the problems, approaches, and results. An important subproblem is the districting problem where the goal is to partition a graph into connected subgraphs of similar ``size'' with the objective to make each subgraph as compact (``round-shaped'') as possible. We overview several methods to measure the compactness and to formulate this problem in terms of integer programs. We dive deep into one formulation that pursues a column generation approach where promising subgraphs are generated iteratively. The problem of identifying such subgraphs is called pricing, and we extensively study this problem of finding a single connected subgraph that is subject to various constraints. Powerful preprocessing methods, strengthening cuts that support the dual side of the problem, and different primal heuristics are proposed to help the solution process. In a broad computational study, we prove the effectiveness of these methods on real-life and artificial instances. The motivating application for this study is concerned with the optimal design of toll control sections on German motorways. We transform it into a districting problem and apply the developed techniques within a branch-and-price-and-cut approach. The computational analysis shows that only with the proposed contributions, we are able to solve all of the design problems in several seconds, whereas without these improvements, the computation times are larger by magnitudes and can take hours.