Structural graph theory meets algorithms: covering and connectivity problems in graphs
Saeed Akhoondian Amiri · DepositOnce · 2017
Structural graph theory proved itself a valuable tool for designing efficient algorithms for hard problems over recent decades. We exploit structural graph theory to provide novel techniques and algorithms for covering and connectivity problems. First, we focus on the Local model of distributed computing. In the Local model, minimizing the number of communication rounds is the main goal. We exploit the local properties of bounded genus graphs. We provide the first constant factor approximation algorithm that solves the dominating set problem in constant rounds on bounded genus graphs. Then, we arbitrarily well approximate it in O(log^*|G|) rounds. We also introduce a simple technique for graphs of bounded expansion which turns any constant factor approximation of r-dominating sets to a constant factor approximation of connected r-dominating sets. Finding similar patterns in graphs is one of the main challenges in graph theory. One such problem is either to find many disjoint instances of a particular pattern or to find a small set of vertices such that deleting them destroys all instances of that pattern. This question first raised by Erdos and Posa. We provide an algorithmic classification for strongly connected digraphs analogous to the classical results of Robertson and Seymour on undirected graphs. Furthermore, a good characterization for vertex cyclic digraphs is provided. In the latter, we generalize Younger's conjecture to weakly connected digraphs. Next, we focus on routing and connectivity problems. The first routing problem we consider is the VDPP and its descendant problems. We provide an efficient algorithm for solving VDPP{k} on upward planar digraphs in linear time for a fixed k. Then we allow the vertices to have some congestion and we solve the VDPP with congestion in acyclic digraphs. On the complexity side, we show the hardness of those problems when the corresponding parameter (e.g. $k$) is part of the input. It follows that the time complexity of our algorithms are almost optimal. We also show that induced path problem is hard even on digraphs of bounded directed tree-width. Finally, we consider the problem of rerouting. In a computer network, we may need to reroute packets from their old paths to new paths. The rerouting procedure should satisfy some consistency rules. E.g., the capacity of links should be respected, the flow of the packets cannot be interrupted, etc. Elements of the network are asynchronous. Thus, it is not possible to do the rerouting instantly. We show that it is NP-hard to find a feasible rerouting algorithm even on DAGs. In contrast, we provide a linear time rerouting algorithm on acyclic graphs for a fixed number of paths.