Scalable Algorithms for 2-Packing Sets on Arbitrary Graphs

Abstract

A 2-packing set for an undirected graph $G=(V,E)$ is defined as a subset $\mathcal{S}\subseteq V$ such that for each pair of vertices $v_1 \neq v_2 \in \mathcal{S}$, the shortest path between $v_1$ and $v_2$ has at least length three. Finding a 2-packing set of maximum cardinality is an NP-hard problem. We develop a new approach to solve this problem on arbitrary graphs using its close relation to the independent set problem. Our approach uses new data reduction rules as well as a graph transformation. Experiments show that this technique outperforms the state-of-the-art for arbitrary graphs with respect to solution quality. Furthermore, we can compute solutions multiple orders of magnitude faster than previously possible. Our approach solves 63% of the graphs in the tested data set to optimality in under a second. In contrast, the competitor for arbitrary graphs can only solve 5% of these graphs to optimality even with a 10-hour time limit. Moreover, our approach can solve a wide range of large instances that have previously been unsolved.