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.

A (fully) dynamic graph algorithm is a data structure that supports edge insertions, edge deletions, and answers specific queries pertinent to the problem at hand. In this work, we address the fully dynamic edge orientation problem, also known as the fully dynamic \(\Delta\)-orientation problem. The objective is to maintain an orientation of the edges in an undirected graph such that the out-degree of any vertex remains low. When edges are inserted or deleted, it may be necessary to reorient some edges to prevent vertices from having excessively high out-degrees. In this paper, we introduce the first algorithm that maintains an optimal edge orientation during both insertions and deletions. In experiments comparing with recent nearly exact algorithms, we achieve a 32% lower running time. The update time of our algorithm is up to 6 orders of magnitude faster than static exact algorithms.

Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating recently developed approximation algorithms for dynamically maintaining graph orientations. We comprehensively describe the underlying data structures, including efficient bucketing techniques and round-robin updates. Our implementation has a natural parameter $λ$, which allows for a trade-off between algorithmic efficiency and the quality of the solution. In the extensive experimental evaluation, we demonstrate that our implementation offers a considerable speedup. Using different quality metrics, we show that our implementations are very competitive and can outperform previous methods. Overall, our approach solves more instances than other methods while being up to 112 times faster on instances that are solvable by all methods compared.

Learn and Reduce Dataset This dataset consists of vertex-labeled graphs used to train machine learning models for data reduction screening. This is used as a preprocessing step to solve the Maximum Weight Independent Set problem. The original folder contains all instances and reduction data using the computationally cheap reduction rules. The graphs and reduction data are stored as two separate CSV files, with the suffix _original_graph.csv and _original_reduction_data.csv. Similarly, the kernel folder contains the non-empty reduced instances. Here, we use the suffix _kernel_graph.csv and _kernel_reduction_data.csv. The graph files have two columns, source and target. Each undirected edge {u,v} in the graph appears as both u;v and v;u.

Computing maximum weight independent sets in graphs is an important NP-hard optimization problem. The problem is particularly difficult to solve in large graphs for which data reduction techniques do not work well. To be more precise, state-of-the-art branch-and-reduce algorithms can solve many large-scale graphs if reductions are applicable. Otherwise, their performance quickly degrades due to branching requiring exponential time. In this paper, we develop an advanced memetic algorithm to tackle the problem, which incorporates recent data reduction techniques to compute near-optimal weighted independent sets in huge sparse networks. More precisely, we use a memetic approach to recursively choose vertices that are likely to be in a large-weight independent set. We include these vertices into the solution, and further reduce the graph. We show that identifying and removing vertices likely to be in large-weight independent sets opens up the reduction space and speeds up the computation of large-weight independent sets remarkably. Our experimental evaluation indicates that we are able to outperform state-of-the-art algorithms. For example, our two algorithm configurations compute the best results among all competing algorithms for 205 out of 207 instances. Thus can be seen as a useful tool when large-weight independent sets need to be computed in practice.

This paper proposes multiple extensions to the popular bicriterion transit routing approach -- Trip-Based Transit Routing (TBTR). Specifically, building on the premise of the HypRAPTOR algorithm, we first extend TBTR to its partitioning variant -- HypTBTR. However, the improvement in query times of HyTBTR over TBTR comes at the cost of increased preprocessing. To counter this issue, two new techniques are proposed -- a One-To-Many variant of TBTR and multilevel partitioning. Our One-To-Many algorithm can rapidly solve profile queries, which not only reduces the preprocessing time for HypTBTR, but can also aid other popular approaches such as HypRAPTOR. Next, we integrate a multilevel graph partitioning paradigm in HypTBTR and HypRAPTOR to reduce the fill-in computations. The efficacy of the proposed algorithms is extensively tested on real-world large-scale datasets. Additional analysis studying the effect of hypergraph partitioning tools (hMETIS, KaHyPar, and an integer program) along with different weighting schemes is also presented.

Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. We survey recent trends in data reduction engineering results for selected problems. Moreover, we describe concrete techniques that may be useful for future implementations in the area and give open problems and research questions.