The maximum independent set (MIS) problem is a fundamental NP-hard optimization problem that remains challenging on large graphs. Machine learning (ML) offers the potential to aid algorithm designers in rapidly developing effective heuristics across problem variants and input distributions. However, existing end-to-end ML approaches often struggle with generalization, require extensive training data, and are rarely designed to scale to extremely large problem instances. We propose a hybrid ML–algorithmic framework that follows the Learning to Prune (LTP) paradigm: a classifier predicts vertices to fix (or prune) and the instance is simplified, before applying a state-of-the-art solver. A key challenge in this setting is due to the fact that Linear Programming Relaxation-derived features—crucial in many LTP pipelines—are often too slow and too coarse to be practical for MIS at scale. We overcome this by adapting the multiplicative weights method from the theoretical computer science literature, yielding fast, high-quality surrogate features that preserve the key structural signal of the linear programming relaxation. We showcase the flexibility of this generic technique by extending our approach to the $$3$$ -path vertex cover problem ( $$VCP_3$$ ). For MIS experiments, we utilize the state-of-the-art ReduMIS solver, which is capable of producing high quality solutions even on massive graphs. Results show that training on only about one hundred graph instances with ReduMIS solutions suffices for our method to achieve solutions within 10% of those obtained by ReduMIS on the test set, while running in roughly half the time, especially on dense graphs. In experiments on $$VCP_3$$ , the learned models yield even stronger scalability and practical gains. We adopt the highest ranked heuristic solver from the PACE 2025 challenge for this problem. We show that on large test instances, our classifiers are powerful enough to admit aggressive vertex pruning, yielding solutions that are on average $$5\%$$ better than the state-of-the-art PACE heuristic baseline in half of the runtime.

Abstract In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs—the simultaneous version of arguably one of the most well-studied graph classes—is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more ‘rigid’ and therefore have less freedom in their representation. We show they can be recognized in time $$\mathcal {O}(|V|\cdot |E|)$$ O ( | V | · | E | ) for any number of simultaneous graphs in the sunflower case where $$G=(V,E)$$ G = ( V , E ) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

The edge clique cover (ECC) problem - where the goal is to find a minimum cardinality set of cliques that cover all the edges of a graph - is a classic NP-hard problem that has received much attention from both the theoretical and experimental algorithms communities. While small sparse graphs can be solved exactly via the branch-and-reduce algorithm of Gramm et al. [JEA 2009], larger instances can currently only be solved inexactly using heuristics with unknown overall solution quality. We revisit computing minimum ECCs exactly in practice by combining data reduction for both the ECC and vertex clique cover (VCC) problems. We do so by modifying the polynomial-time reduction of Kou et al. [Commun. ACM 1978] to transform a reduced ECC instance to a VCC instance; alternatively, we show it is possible to "lift" some VCC reductions to the ECC problem. Our experiments show that combining data reduction for both problems (which we call synergistic data reduction) enables finding exact minimum ECCs orders of magnitude faster than the technique of Gramm et al., and allows solving large sparse graphs on up to millions of vertices and edges that have never before been solved. With these new exact solutions, we evaluate the quality of recent heuristic algorithms on large instances for the first time. The most recent of these, EO-ECC by Abdullah et al. [ICCS 2022], solves 8 of the 27 instances for which we have exact solutions. It is our hope that our strategy rallies researchers to seek improved algorithms for the ECC problem.

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.

The vertex clique cover (VCC) problem—the problem of computing a minimum cardinality set of cliques covering all vertices of a graph—is a classic NP-hard problem. Despite recent advances in parameterized algorithms that have been used to solve NP-hard problems in practice, the VCC problem has been almost completely unexplored. In particular, data reduction rules, which transform the input graph to a smaller equivalent instance, are well studied and highly effective at solving other NP-hard problems (e.g., the minimum vertex cover problem) in practice on sparse graphs of millions of vertices. Practical rules for the VCC problem, on the other hand, are nearly nonexistent: instead, the complementary graph coloring problem has received the lion's share of attention, and the available rules for that problem are either theoretical or they do not translate to effective rules for solving the VCC problem on sparse graphs. In this paper, we introduce a large suite of data reduction rules for the VCC problem. These rules enable us to solve large, sparse, real-world graphs significantly faster than the state of the art. Of the 52 graphs tested, without any additional techniques, our reduction rules completely solve 14 graphs with up to 326K vertices in a few milliseconds. Furthermore, applying our rules as a preprocessing step accelerates the state-of-the-art iterated greedy (IG) approach due to Chalupa, enabling us to find higher-quality solutions up to multiple orders of magnitude faster than previously possible. Furthermore, we integrate our data reductions into the branch-and-reduce framework, exactly solving instances on up to millions of vertices. As an added bonus, our data reduction rules partially explain why the clique cover number and independence number have been observed to match for many sparse instances—our data reduction rules apply to both the maximum independent set and VCC problems.

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.

The k -plex model is a relaxation of the clique model by allowing every vertex to miss up to k neighbors. Designing exact and efficient algorithms for computing a maximum k -plex in a graph has been receiving increasing interest recently. However, the existing algorithms are still inefficient due to having major limitations. We in this paper design a new algorithm kPlexS for the maximum k -plex problem, with three novel contributions. Firstly, we propose a new framework for computing maximum k -plex over large sparse graphs, by iteratively extracting small dense subgraphs from it and then solving each of the extracted dense subgraphs by a branch-and-bound search. Secondly, we propose an efficient reduction algorithm CTCP to reduce the input graph size by exhaustively conducting vertex reduction and edge reduction. CTCP computes a smaller reduced graph and also has a lower time complexity than the existing techniques. Moreover, we iteratively invoke CTCP to reduce the input graph once a vertex has been processed and removed from it. Thirdly, we develop a branch-and-bound algorithm BBMatrix specifically targeting the dense subgraphs that are extracted from the input graph. BBMatrix represents its input graph by an adjacency matrix, and utilizes both first-order (i.e., individual vertices) and second-order information (i.e., pairs of vertices) for reduction and upper bounding. In addition, incremental techniques are proposed to efficiently apply the reduction and upper bounding during the recursion. Extensive empirical studies on large real graphs demonstrate that our algorithm kPlexS outperforms the state-of-the-art algorithms BnB, Maplex, and KpLeX.

Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto standard approach to solve the problem to optimality in practice. In this paradigm, data reduction rules are applied to decrease the problem size. These data reduction rules ensure that given an optimum solution on the new (smaller) input, one can quickly construct an optimum solution on the original input. We introduce new generalized data reduction and transformation rules for the problem. A key feature of our work is that some transformation rules can increase the size of the input. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later throughout the algorithm. In experiments, our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than heuristic solvers DynWVC and HILS on many instances. While the increasing transformations are only efficient enough for preprocessing at this time, we see this as a critical initial step towards a new branch-and-transform paradigm.

Many applications rely on solving sparse linear systems, which can be sped up significantly by permuting the matrix to minimize the number of non-zeros introduced by factorization—the fill-in. Equivalently, one can compute an elimination order of the graph that minimizes the number of introduced edges, for which the fast but inexact nested dissection algorithm is often used in practice. In this paper, we engineer new data reduction rules for the minimum fill-in problem, which significantly reduce the size of the graph while producing an equivalent (or near-equivalent) instance. By applying both new and existing data reduction rules exhaustively before nested dissection, we obtain improved quality and at the same time large improvements in running time on a variety of instances. For example, on road networks, where nested dissection algorithms are typically used as a preprocessing step for shortest path computations, our algorithms are on average six times faster than Metis while computing orderings with less fill-in.

This paper explores techniques to quickly solve the maximum weight clique problem (MWCP) in very large scale sparse graphs. Due to their size, and the hardness of MWCP, it is infeasible to solve many of these graphs with exact algorithms. Although recent heuristic algorithms make progress in solving MWCP in large graphs, they still need considerable time to get a high-quality solution. In this work, we focus on solving MWCP for large sparse graphs within a short time limit. We propose a new method for MWCP which interleaves clique finding with data reduction rules. We propose novel ideas to make this process efficient, and develop an algorithm called FastWClq. Experiments on a broad range of large sparse graphs show that FastWClq finds better solutions than state-of-the-art algorithms while the running time of FastWClq is much shorter than the competitors for most instances. Further, FastWClq proves the optimality of its solutions for roughly half of the graphs, all with at least 105 vertices, with an average time of 21 seconds.

Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application of data reduction rules. For the fundamental Max Cut problem, kernelization algorithms are theoretically highly efficient for various parameterizations. However, the efficacy of these reduction rules in practice—to aid solving highly challenging benchmark instances to optimality—remains entirely unexplored. We engineer a new suite of efficient data reduction rules that subsume most of the previously published rules, and demonstrate their significant impact on benchmark data sets, including synthetic instances, and data sets from the VLSI and image segmentation application domains. Our experiments reveal that current state-of-the-art solvers can be sped up by up to multiple orders of magnitude when combined with our data reduction rules. On social and biological networks in particular, kernelization enables us to solve four instances that were previously unsolved in a ten-hour time limit with state-of-the-art solvers; three of these instances are now solved in less than two seconds.

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.

One powerful technique to solve NP-hard optimization problems in practice is branch-and-reduce search—which is branch-and-bound that intermixes branching with reductions to decrease the input size. While this technique is known to be very effective in practice for unweighted problems, very little is known for weighted problems, in part due to a lack of known effective reductions. In this work, we develop a full suite of new reductions for the maximum weight independent set problem and provide extensive experiments to show their effectiveness in practice on real-world graphs of up to millions of vertices and edges. Our experiments indicate that our approach is able to outperform existing state-of-the-art algorithms, solving many instances that were previously infeasible. In particular, we show that branch-and-reduce is able to solve a large number of instances up to two orders of magnitude faster than existing (inexact) local search algorithms—and is able to solve the majority of instances within 15 minutes. For those instances remaining infeasible, we show that combining kernelization with local search produces higher-quality solutions than local search alone.

Edge-centric distributed computations have appeared as a recent technique to improve the shortcomings of think-like-a-vertex algorithms on large scale-free networks. In order to increase parallelism on this model, edge partitioning—partitioning edges into roughly equally sized blocks—has emerged as an alternative to traditional (node-based) graph partitioning. In this work, we develop a fast parallel split-and-connect graph construction algorithm in the distributed setting and show that combining our parallel construction with advanced parallel node partitioning algorithms yields high-quality edge partitions in a scalable way. Our technique scales to networks with billions of edges, and runs efficiently on thousands of PEs. Our extensive experiments show that our algorithm computes solutions of high quality on large real-world networks and large hyperbolic random graphs—which have a power law degree distribution and are therefore specifically targeted by edge partitioning.

In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs - the simultaneous version of arguably one of the most well-studied graph classes - is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more "rigid" and therefore have less freedom in their representation. We show they can be recognized in time O(|V|*|E|) for any number of simultaneous graphs in the sunflower case where G=(V,E) is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.

We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance they travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log2⁡n) time for any two query positions s,t where the two persons start.

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.

The most efficient algorithms for finding maximum independent sets in both theory and practice use reduction rules to obtain a much smaller problem instance called a kernel. The kernel can then be solved quickly using exact or heuristic algorithms—or by repeatedly kernelizing recursively in the branch-and-reduce paradigm. It is of critical importance for these algorithms that kernelization is fast and returns a small kernel. Current algorithms are either slow but produce a small kernel, or fast and give a large kernel. We attempt to accomplish both of these goals simultaneously, by giving an efficient parallel kernelization algorithm based on graph partitioning and parallel bipartite maximum matching. We combine our parallelization techniques with two techniques to accelerate kernelization further: dependency checking that prunes reductions that cannot be applied, and reduction tracking that allows us to stop kernelization when reductions become less fruitful. Our algorithm produces kernels that are orders of magnitude smaller than the fastest kernelization methods, while having a similar execution time. Furthermore, our algorithm is able to compute kernels with size comparable to the smallest known kernels, but up to two orders of magnitude faster than previously possible. Finally, we show that our kernelization algorithm can be used to accelerate existing state-of-the-art heuristic algorithms, allowing us to find larger independent sets faster on large real-world networks and synthetic instances.

Computing high quality node separators in large graphs is necessary for a variety of applications, ranging from divide-and-conquer algorithms to VLSI design. In this work, we present a novel distributed evolutionary algorithm tackling the k-way node separator problem. A key component of our contribution includes new k-way local search algorithms based on maximum flows. We combine our local search with a multilevel approach to compute an initial population for our evolutionary algorithm, and further show how to modify the coarsening stage of our multilevel algorithm to create effective combine and mutation operations. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high quality solutions in a short amount of time. Our experiments against competing algorithms show that our advanced evolutionary algorithm computes the best result on 94% of the chosen benchmark instances.

The increased availability of interactive maps on the Internet and on personal mobile devices has created new challenges in computational cartography and, in particular, for label placement in maps. Operations like rotation, zoom, and translation dynamically change the map over time and make a consistent adaptation of the map labeling necessary.

We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having n vertices and k pairwise crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeroes in” on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.