Increasing distances in graphs
Stefan Krause · Digitale Bibliothek Braunschweig (Verbundzentrale Göttingen (VZG)) · 2006
In this work a special Set Cover problem is studied. It has strong links to Min Cut problems, that is, problems where all paths between vertices of given pairs are to be blocked. Here, on the contrary, we only demand that shortest paths (with unit edge lengths) are disconnected. Therefore the goal is to increase distances of given vertex pairs by at least 1 by removing an edge set having minimum cost. This problem is called blocking shortest paths. For some special cases polynomial time algorithms are given, and it is shown that in most other cases the problem is NP-complete. Motivated by this result we show how to solve this problem exactly using mixed integer programming, and we present approximation algorithms. For the latter one we determine best possible performance guarantees or give at least almost tight bounds. The given algorithms are tested for random instances. In addition extremal problems of this area are discussed.