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

A Parallel Evolutionary Algorithm Framework for Graph $k$-CUT Problems

A unified Parallel Evolutionary Algorithm Framework (PEAF) is proposed, which combines structure-inheriting crossover operators, a hierarchical mutation mechanism based on the Multiple Mutation Heuristic and the Auxiliary Cut Mutation Heuristic, and a diversity-preserving selection strategy.

Scalable Exact Densest P-Partite Subgraph Search in Heterogeneous Information Networks

BoxDPpS performs box-level search with safe region pruning, eliminates redundant representations of the same iRM-set, improves early pruning through bounded warm-up, and compresses each fixed-M auxiliary network for exact parametric pseudoflow solving.

LLM-Driven Joint Evolution of Coupled Heuristics Components for Routing Optimization

Heuristic design for combinatorial optimization remains heavily reliant on expert knowledge, while existing large language model (LLM)-enhanced evolutionary methods typically evolve isolated algorithmic components, even when one determines the search state on which another operates. This paper proposes LLM-driven Heuristic Components Joint Generation (LLM-HCJG), a population-based framework that jointly generates and co-evolves interdependent heuristic components under a shared design blueprint. Applied to guided local search (GLS), LLM-HCJG couples solution initialization with penalty construction and embeds the generated pair into an enhanced online search mechanism. The resulting form is further transferred from the traveling salesman problem (TSP) to the capacitated vehicle routing problem (CVRP). Theoretical analysis establishes the non-separable state-transition effects between the two components and the advantage in generation consistency. Across synthetic instances and 41 public TSPLIB/CVRPLIB benchmarks, LLM-HCJG attains consistently low optimality gaps, including best or tied-best results on 28 of 29 TSPLIB instances and all 12 CVRPLIB instances. Ablation and structural analyses further indicate that these gains are associated with cross-component compatibility and alignment rather than isolated-component recombination. These results support effective cross-instance transfer within the evaluated routing settings under limited-sample, modest-cost training.

Listing Minimal Cores in Large Real-World Graphs

Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.

An Efficient Cooperative Scatter Search for the Large-Scale k-Clustering Minimum Biclique Completion Problem

The k-Clustering Minimum Biclique Completion Problem (k-CMBCP) is an NP-hard combinatorial optimization problem with significant implications in bipartite graph clustering applications. The objective is to partition a set of services into k disjoint clusters such that the number of missing edges required to transform each cluster into a complete biclique is minimized. This paper proposes a robust Cooperative Scatter Search (CSS) algorithm designed to exploit the structural characteristics of the problem. The proposed metaheuristic framework integrates a diversification-based population initialization strategy, dynamic management of elite reference set, and a specialized uniform-based recombination operator. Furthermore, the algorithm incorporates a sequential Variable Neighborhood Descent (VND) strategy leveraging three complementary neighborhoods to intensify the local search. The contribution is a problem-tailored integration of known search ingredients rather than a generic new metaheuristic paradigm: its novelty lies in the way diversification, reference-set memory, recombination, and SeqVND are coordinated for the specific structure of the k-CMBCP. Computational experiments on benchmark instances show that the proposed method achieves competitive and superior performance compared with recent heuristics in terms of solution quality and computational stability.

A Parallel Framework for the Maximum Common Induced Subgraph Problem