Finding maximum-weight independent sets in graphs is an important NP-hard optimization problem. Given a vertex-weighted graph \(G\), the task is to find a subset of pairwise non-adjacent vertices of \(G\) with maximum weight. Most recently published practical exact algorithms and heuristics for this problem use a variety of data-reduction rules to compute (near- )optimal solutions. Applying these rules results in an equivalent instance of reduced size. An optimal solution to the reduced instance can be easily used to construct an optimal solution for the original input.

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.

A dynamic graph algorithm is a data structure that supports edge insertions, deletions, and problem specific queries. While extensive research exists on dynamic algorithms for graph problems solvable in polynomial time, most of these algorithms have not been implemented or empirically evaluated. This work addresses the NPcomplete maximum weight as well as the maximum cardinality independent set problem in a dynamic setting, applicable to areas like dynamic map-labeling and vehicle routing. In this work, specifically we introduce a novel local search technique called optimal neighborhood exploration. This technique creates independent subproblems that are solved to optimality, leading to improved overall solutions. Through numerous experiments, we assess the effectiveness of our approach and compare it with other state-of-the-art dynamic solvers. Our algorithm features a parameter, the subproblem size, that balances running time and solution quality.