HP-MC: Quickly Computing Maximum Clique Sizes of Large Sparse Graphs

Scalable Graph Coreset Selection via Greedy Sampling

This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.

Average Distance Approximation for Static Large Graphs

The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.

An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs

The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$ or a red clique of size $n$. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that avoids both cliques. We develop an integer programming framework for certifying such lower bounds, restricting the search to circulant graphs, whose rotational symmetry lets us reformulate the problem in a projected distance space, reducing the number of binary variables from quadratic to linear in the graph order. We strengthen this projected model through coefficient reduction and solve it with a branch-and-cut algorithm whose separation routine exploits the common neighborhood structure of circulant graphs, combining heuristic and exact maximum-clique algorithms. In an extensive computational campaign on circulant graphs with up to 410 vertices, we improve the best lower bounds previously obtained by other methods by up to 11 points for 25 values of $R(3,n)$ with $24\le n\le49$ and $n\neq27$, each backed by an explicit graph certificate that can be independently verified with a stand-alone exact clique solver. To the best of our knowledge, our method also provides the first reproducible optimization-based procedure for certifying circulant Ramsey numbers $R_C(m,n)$, which we use to establish eight new values of $R_C(3,n)$ with $13\le n\le20$. Our framework, graph certificates, and stand-alone checker are provided as supplementary material to support independent verification and reuse.

Partially-Dynamic Maximum Flow in Dense Graphs

Cooperative Multi-Heuristic Parallelization for the Maximum Common Induced Subgraph Problem

: The Maximum Common Induced Subgraph problem is a central challenge in combinatorial optimization, with applications across diverse fields. Its NP-hard nature has led to a long line of branch-and-bound algorithms, among which the McSplit family stands out for its search-space representation and effective pruning. More recent extensions, such as McSplit-DAL, integrate Domain Action Learning to guide branching decisions us-ing dynamic reward functions. However, they remain essentially sequential and rely on a single heuristic configuration, underutilizing modern multi-core architectures and heuristic diversification. In this work, we introduce CP-McSplitDAL, a cooperative parallel framework that extends McSplit-DAL with portfolio-style multi-heuristic search on shared-memory machines. The original recursive algorithm is reformulated as an iterative engine, enabling explicit management of search states, load sharing among threads, and controlled thread migration between heuristics. Each context couples a topological vertex-ranking metric with a specific ordering scheme and learns its own reward landscape. Cooperation is achieved through a globally shared variable that represents the size of the largest solution found so far, enabling cross-heuristic pruning and adaptive reward handling, and supporting both unified and distributed matrices. At the same time, a master evaluation periodically decays rewards and deactivates under-performing heuristics, shifting from early diversification to late exploitation. We evaluate CP-McSplitDAL on standard benchmarks, including small instances solvable to optimality and a large set of real-world graph pairs. The results show that our cooperative multi-heuristic configuration achieves lower regret in time to optimality, improves solution quality under time limits, and better exploits multi-core hardware than non-cooperative or purely sequential variants.

Exponential Energy Savings in Local Distributed Graph Algorithms

This paper investigates the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover. We present randomized distributed algorithms that, while having round complexity almost matching the respective state of the art, achieve nearly exponentially smaller energy complexity. That is, in each of these algorithms, each node is awake for only an exponentially small fraction of the time, and the round complexity still remains almost the same as the best-known algorithm. During the rest of the rounds, the node does not perform any computation or communication (and any messages sent to it at that time go unheard). Some of our concrete results are as follows: • For (1 + ε)-approximate maximum matching and (2 + ε)-approximate minimum vertex cover, with any arbitrary constant ε > 0, we get energy complexity O(log log n) while retaining the familiar O(log n) round complexity. • For low out-degree orientation of edges, we get maximum outdegree O(λ)—where λ denotes the graph's arboricity—with O(log log n) energy complexity and in the familiar O(log n) round complexity, though assuming λ = Ω(log2 n). • We get linear size spanners with stretch O(log1+ε n), using O(log log n) energy and O(log1+ε n) rounds. These round complexity and stretch bounds almost match the familiar O(log n) bounds.