💻 computer science

A Path Relinking Metaheuristic for the Capacitated Vertex Separator Problem

This paper introduces a path relinking metaheuristic enhanced with label matching and component moves to efficiently solve the Capacitated Vertex Separator Problem, demonstrating superior performance over existing exact algorithms by matching optimal solutions in most cases and improving upper bounds in the remainder.

Original authors: Sergiu Amihaesei

Published 2026-10-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sergiu Amihaesei

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast network of cities connected by roads, where the goal is to isolate specific regions from one another by closing down a minimal number of intersections. In the world of computer science and mathematics, this is known as a graph, where the cities are points and the roads are lines connecting them. Sometimes, engineers need to break such a network into separate, manageable chunks, perhaps to speed up calculations or to make a system more reliable. The challenge is to remove as few intersections as possible while ensuring that no two resulting chunks are still connected by a road, and that no single chunk becomes too large to handle. This specific puzzle, where the size of each chunk is strictly limited, is called the Capacitated Vertex Separator Problem. It is a difficult task, one that computers struggle to solve perfectly when the network grows large, often leaving researchers with good guesses but no guarantee that they have found the absolute best solution.

A researcher named Sergiu Amihaesei has developed a new method to tackle this problem more effectively. Instead of trying to calculate every possible way to cut the network, which would take too long, the new approach uses a strategy called path relinking. Think of this as taking two different, already decent ways of cutting the network and exploring the space between them. The computer starts with one solution and gradually transforms it into the other, step by step. At every single step of this transformation, the computer checks to make sure the rules are still being followed: no chunk is too big, and no two chunks are accidentally touching. By carefully navigating this path, the method often discovers a way to cut the network that uses even fewer intersections than either of the starting solutions.

The key innovation in this work is how the computer handles the labels of these chunks. In a network, the chunks are interchangeable; swapping the names of two chunks does not change the solution. However, if the computer does not account for this, it might waste time trying to fix differences that are just a matter of naming. The new method first matches the chunks between the two starting solutions to see which ones correspond to each other, ensuring the transformation is efficient. Furthermore, instead of moving just one city at a time, the method can move entire clusters of connected cities in a single step if they all belong to the same destination. This prevents the computer from getting stuck in dead ends where a solution is temporarily broken and cannot be fixed.

To test this approach, the researcher applied it to a large collection of 89 different network maps, testing each one with nine different rules for how many chunks to create. This resulted in 801 distinct scenarios to solve. The results were compared against the best existing methods, which are known for being very precise but sometimes slow. In cases where the old methods had already found the perfect answer, the new method matched that perfection in 608 out of 611 instances. More importantly, in the 190 cases where the old methods could not find the perfect answer and stopped with a "best guess," the new method improved that guess in 145 cases, finding a way to remove fewer intersections than anyone had previously managed.

The study also included a careful look at which parts of the new method were actually doing the heavy lifting. The researchers tested the system by removing specific features, such as the ability to match chunk names or the ability to move whole clusters at once. They found that without the name-matching feature, the computer had to take many more steps to get from one solution to another, and without the cluster-moving feature, the final results were often worse. This confirmed that both features were essential for the method's success. The research concludes that while the problem is not fully solved for every possible scenario, this new path relinking technique provides a powerful tool for finding better solutions faster, offering a significant improvement over previous attempts for a wide range of network sizes.

Technical Summary: A Path Relinking Metaheuristic for the Capacitated Vertex Separator Problem

Problem Definition
The Capacitated Vertex Separator Problem (CVSP) is defined on an undirected graph $G=(V, E)$ with $n$ vertices and two integers, $k$ and $b$ . The objective is to remove a minimum number of vertices (the separator $S$ ) such that the remaining vertices are partitioned into at most $k$ non-adjacent subsets, called shores ( $V_0, \dots, V_{k-1}$ ), where no shore exceeds capacity $b$ . The problem is NP-hard. This study focuses on the balanced unweighted case where every vertex has equal weight and the capacity is fixed at $b = \lceil n/k \rceil$ .

A critical distinction of CVSP from the classical two-shore Vertex Separator Problem (VSP) is the packing condition. Once a separator is removed, the remaining graph consists of connected components. A separator is feasible only if these components can be assigned entirely to the $k$ shores such that no shore exceeds capacity $b$ . This requires solving a bin-packing subproblem; simply ensuring each component fits individually in a shore is insufficient. Additionally, shore labels are interchangeable, meaning a solution with $k$ shores has up to $k!$ equivalent labelings.

Methodology
The author proposes a path relinking metaheuristic that extends the PR-VSP algorithm (originally designed for two shores) to handle $k$ interchangeable shores with capacity constraints. The search structure maintains a reference set of diverse, high-quality solutions. In each iteration, pairs of solutions are selected to generate a path of intermediate solutions, with the best path solution subsequently improved via Tabu Search.

Key methodological innovations include:

Maximum Overlap Shore Matching: Before constructing a path between an initiating solution $x$ and a guiding solution $g$ , the algorithm computes a bijection $\pi$ between the shore labels of $g$ and $x$ that maximizes the overlap of vertices in corresponding shores. This alignment minimizes the initial "mismatch" (the number of moves required to transform $x$ into the aligned $g$ ) and prevents the path from wasting moves correcting arbitrary label permutations.
Feasible Relinking Moves: The path construction ensures that every intermediate solution is feasible. The algorithm employs four move types:
- Delete: Moves a vertex from a shore to the separator.
- Insert: Moves a vertex from the separator to a shore (if capacity permits and no inter-shore edges are created).
- Buffer: Moves a vertex from a "wrong" shore to the separator to prepare for insertion.
- ComponentTransfer: Moves an entire connected component from one shore to another in a single operation, provided the destination has sufficient capacity.
Canonical Representation: To handle interchangeable labels, solutions are stored and compared using a canonical representation (sorting vertices within shores and sorting the shore lists themselves). This ensures the reference set does not fill with duplicate solutions differing only by label permutation.
Termination and Feasibility Guarantees: The author proves that every solution on the relinking path remains feasible and that the path reaches the aligned guiding solution in at most $2n$ moves.

Key Contributions

Algorithmic Extension: The first dedicated metaheuristic for CVSP, extending PR-VSP to $k$ shores by integrating shore matching and component transfers.
Feasibility Preservation: A path construction strategy that guarantees all intermediate solutions satisfy both separation and capacity (packing) constraints, eliminating the need for repair steps that might fail.
Computational Evaluation: A comprehensive evaluation on 801 combinations of 89 graph instances (DIMACS and random hypergraph clique expansions) across nine values of $k$ .

Experimental Results
The metaheuristic was run 10 times per combination (8,010 total runs) and compared against the exact branch-and-cut algorithm of Furini et al. (2022) and a local rerun of that algorithm.

Optimality: Among the 611 combinations where the exact algorithm found the optimum, the metaheuristic matched the optimum in 608 cases.
Improvements: For the 190 combinations where the exact algorithm failed to find an optimum (open instances), the metaheuristic improved the best known upper bound in 145 cases.
Ablation Study: A study comparing the full algorithm against reduced configurations revealed:
- Removing shore matching increased path lengths and reduced the number of matched optima by 5.
- Removing component transfers significantly degraded performance, reducing matched optima by 13 and increasing the mean gap above the bound.
- Removing soft restarts had negligible impact.
- A "Tabu only" configuration (without path relinking) performed significantly worse, matching 41 fewer optima and improving 3 fewer bounds.

Significance and Limitations
The paper claims that the proposed metaheuristic effectively addresses the specific challenges of CVSP, particularly the packing condition and label interchangeability, which existing exact methods struggle with within time limits. The method provides high-quality upper bounds for instances where exact methods fail to converge.

The author modestly notes several limitations:

The results are specific to the balanced, unweighted case with $b = \lceil n/k \rceil$ .
The 145 improved upper bounds are not proven optimal; the true optimum for these instances remains unknown.
The Tabu Search parameters were inherited from the two-shore PR-VSP and not specifically tuned for CVSP.
The experimental instances are limited to $n \leq 496$ ; performance on much larger graphs or weighted variants is not established.
The random instances used are clique expansions of hypergraphs; direct search on hypergraphs was not performed.

The author suggests that the high-quality solutions generated can serve as primal bounds for exact methods to potentially close the remaining open instances.

Technical Summary: A Path Relinking Metaheuristic for the Capacitated Vertex Separator Problem

More like this