Finding Maximum Weight 2‐Packing Sets on Arbitrary Graphs

Le résumé fourni par la source

ABSTRACT A 2‐packing set for an undirected, weighted graph is a subset such that any two vertices are not adjacent and have no common neighbors. The Maximum Weight 2‐Packing Set problem that asks for a 2‐packing set of maximum weight is ‐hard. Next to 13 novel data reduction rules for this problem, we develop two new approaches to solve this problem on arbitrary graphs. First, we introduce a preprocessing routine that exploits the close relation of 2‐packing sets to independent sets. This makes well‐studied independent set solvers usable for the Maximum Weight 2‐Packing Set problem. Second, we propose an iterative reduce‐and‐peel approach that utilizes the new data reductions. Our experiments show that our preprocessing routine gives speedups of multiple orders of magnitude, while also improving solution quality and memory consumption compared to a naive transformation to independent set instances. Furthermore, it solves 44% of the instances tested to optimality. Our heuristic can keep up with the best‐performing maximum weight independent set solvers combined with our preprocessing routine. Additionally, our heuristic can find the best solution quality on the biggest instances in our data set, outperforming all other approaches. When using our data reduction rules for exact solvers, we can solve more instances to optimality and are overall multiple orders of magnitude faster.

Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.