Car

TL;DR

• Simplifies complex graphs by randomly merging pairs of vertices to create a smaller, coarsened graph.
• Enables fast, approximate solutions that can be refined later by uncoarsening and local refinement.
• Commonly used in algorithms for minimum cuts and multilevel graph partitioning.

Definition

Coarsening at random is a technique used in computer science, particularly in the domain of graph algorithms, that simplifies a complex graph by merging together (coarsening) pairs of vertices in the graph.

Explanation

Coarsening at random reduces the size and complexity of a graph by selecting pairs of vertices—often at random—and merging them into single vertices. The resulting coarsened graph has fewer vertices, which can make subsequent algorithms faster or more tractable. After processing the coarsened graph, the solution can be projected back to the original graph by uncoarsening (splitting merged vertices) and refining the result.

Examples

Contraction algorithm (minimum cut)

• Given a graph with vertices and edges:
  1. Pick a pair of vertices in the graph at random and merge them together, resulting in a new, coarsened graph with one fewer vertex.
  2. Repeat this process until only two vertices remain in the graph.
• The minimum cut of the original graph is then defined as the set of edges that were removed during the coarsening process.

Multilevel algorithm (graph partitioning)

• Given a graph with vertices and edges:
  1. Coarsen the graph by merging pairs of vertices at random until the graph has a small number of vertices (e.g. 10-20% of the original number of vertices).
  2. Use a graph partitioning algorithm (such as “Kernighan-Lin” or “Fiduccia-Mattheyses”) to partition the coarsened graph into a number of clusters.
  3. Uncoarsen the graph by repeatedly splitting each cluster in the coarsened graph into two sub-clusters, until the original graph is obtained.
  4. Use the partitioning of the coarsened graph as a starting point for refining the partitioning of the original graph.

Use cases

• Finding minimum cuts in a graph (example: contraction algorithm).
• Solving problems related to minimum-cost flow or determining circuit configurations.
• Partitioning a circuit for efficient layout.
• Dividing a computer network into clusters for improved communication.

Notes or pitfalls

• Coarsening at random yields a fast, approximate solution that typically requires additional, more computationally intensive refinement after uncoarsening to improve accuracy.

Related terms

• Contraction algorithm
• Multilevel algorithm
• “Kernighan-Lin”
• “Fiduccia-Mattheyses”
• Graph partitioning
• Minimum cut