Betweenness is a well-known centrality measure that ranks the nodes according to their participation in the shortest paths of a network. In several scenarios, having a high betweenness can have a positive impact on the node itself. Hence, in this paper we consider the problem of determining how much a vertex can increase its centrality by creating a limited amount of new edges incident to it. In particular, we study the problem of maximizing the betweenness score of a given node - Maximum Betweenness Improvement (MBI) - and that of maximizing the ranking of a given node - Maximum Ranking Improvement (MRI). We show that MBI cannot be approximated in polynomial-time within a factor 1-1/(2e) and that MRI does not admit any polynomial-time constant factor approximation algorithm, both unless P=NP. We then propose a simple greedy approximation algorithm for MBI with an almost tight approximation ratio and we test its performance on several real-world networks. We experimentally show that our algorithm highly increases both the betweenness score and the ranking of a given node ant that it outperforms several competitive baselines. To speed up the computation of our greedy algorithm, we also propose a new dynamic algorithm for updating the betweenness of one node after an edge insertion, which might be of independent interest. Using the dynamic algorithm, we are now able to compute an approximation of MBI on networks with up to 105 edges in most cases in a matter of seconds or a few minutes.
Graphical Processing Units have been applied to solve NP- hard problems with no known polynomial time solutions. An example of such a problem is the Traveling Salesman Prob- lem (TSP). The TSP is one of the most commonly studied combinatorial optimization problems and has multiple ap- plications in the areas of engineering, transportation, and logistics. This paper presents an improved algorithm for ap- proximating the TSP on fully connected, symmetric graphs by utilizing the GPU. Our approach improves an existing 2- opt hill-climbing algorithm with random restarts by consid- ering multiple updates to the current path found in parallel, and allows k number of updates per iteration, called k-swap. With our k-swap modification, we show a speed-up over the existing algorithm of 4.5x to 22.9x on data sets ranging from 1400 to 33810 nodes, respectively.
We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto-sense. Our core algorithm heuristically solves the balanced connected st-edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core algorithm as subroutine, we build variants that compute node separators which are independent of s and t. From the computed Pareto-set, we identify cuts with a particularly good trade-off between cut size and balance that can be used to compute contraction and minimum fill-in orders, which can be used in Customizable Contraction Hierarchies (CCH), a speed-up technique for shortest path computations. Our core algorithm runs in O(c|E|) time where $E$ is the set of edges and $c$ the cut size. This makes it well-suited for separating large graphs with small cuts, such as road graphs, which is the primary application motivating our research. For road graphs, we present an extensive experimental study demonstrating that FlowCutter outperforms the current state-of-the-art both in terms of cut sizes and CCH performance. By evaluating FlowCutter on a standard graph partitioning benchmark, we further show that FlowCutter also finds small, balanced cuts on non-road graphs. Another application is the computation of small tree-decompositions. To evaluate our algorithm in this context, we entered the PACE-2016-challenge and won first place in the corresponding sequential competition track. We conlude that FlowCutter finds small, balanced cuts on a wide variety of graphs.