# A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints

arXiv: https://arxiv.org/abs/1902.01534 · HTML: https://mlsanity.com/paper/1902.01534/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2019.

## Built on by (most cited first, 20 of 20)

- [PointDSC: Robust Point Cloud Registration using Deep Spatial Consistency](https://mlsanity.com/paper/2103.05465/) (2021)
- [3D Registration with Maximal Cliques](https://mlsanity.com/paper/2305.10854/) (2023)
- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Advances in Global Solvers for 3D Vision](https://mlsanity.com/paper/2602.14662/) (2026)
- [Efficient and Robust Point Cloud Registration via Heuristics-guided Parameter Search](https://mlsanity.com/paper/2404.06155/) (2024)
- [SG-Reg: Generalizable and Efficient Scene Graph Registration](https://mlsanity.com/paper/2504.14440/) (2025)
- [Multi-instance Point Cloud Registration by Efficient Correspondence Clustering](https://mlsanity.com/paper/2111.14582/) (2021)
- [Optimal and Robust Category-level Perception: Object Pose and Shape Estimation from 2D and 3D Semantic Keypoints](https://mlsanity.com/paper/2206.12498/) (2022)
- [Multi-Model 3D Registration: Finding Multiple Moving Objects in Cluttered Point Clouds](https://mlsanity.com/paper/2402.10865/) (2024)
- [Efficient and Deterministic Search Strategy Based on Residual Projections for Point Cloud Registration with Correspondences](https://mlsanity.com/paper/2305.11716/) (2023)
- [CLIPPER+: A Fast Maximal Clique Algorithm for Robust Global Registration](https://mlsanity.com/paper/2402.15464/) (2024)
- [Scale-Invariant Fast Functional Registration](https://mlsanity.com/paper/2209.12763/) (2022)
- [Instance by Instance: An Iterative Framework for Multi-instance 3D Registration](https://mlsanity.com/paper/2402.04195/) (2024)
- [Correspondence-Free Fast and Robust Spherical Point Pattern Registration](https://mlsanity.com/paper/2508.02339/) (2025)
- [DFC: Deep Feature Consistency for Robust Point Cloud Registration](https://mlsanity.com/paper/2111.07597/) (2021)
- [Fast Semantic-Assisted Outlier Removal for Large-scale Point Cloud Registration](https://mlsanity.com/paper/2202.10579/) (2022)
- [Linearly Solving Robust Rotation Estimation](https://mlsanity.com/paper/2506.11547/) (2025)
- [GMOR: A Lightweight Robust Point Cloud Registration Framework via Geometric Maximum Overlapping](https://mlsanity.com/paper/2508.17427/) (2025)
- [DTIF: Robust Loop Closure Detection via Delaunay Triangle Topology in Complex Forests](https://mlsanity.com/paper/2607.21138/) (2026)

## Abstract (arXiv)

A popular paradigm for 3D point cloud registration is by extracting 3D keypoint correspondences, then estimating the registration function from the correspondences using a robust algorithm. However, many existing 3D keypoint techniques tend to produce large proportions of erroneous correspondences or outliers, which significantly increases the cost of robust estimation. An alternative approach is to directly search for the subset of correspondences that are pairwise consistent, without optimising the registration function. This gives rise to the combinatorial problem of matching with pairwise constraints. In this paper, we propose a very efficient maximum clique algorithm to solve matching with pairwise constraints. Our technique combines tree searching with efficient bounding and pruning based on graph colouring. We demonstrate that, despite the theoretical intractability, many real problem instances can be solved exactly and quickly (seconds to minutes) with our algorithm, which makes our approach an excellent alternative to standard robust techniques for 3D registration.