A practical heuristic for finding graph minors

By Jun Cai, William G. Macready, Aidan Roy. arXiv.org, 2014

361 citations recorded by the source corpus.

We present a heuristic algorithm for finding a graph $H$ as a minor of a graph $G$ that is practical for sparse $G$ and $H$ with hundreds of vertices. We also explain the practical importance of finding graph minors in mapping quadratic pseudo-boolean optimization problems onto an adiabatic quantum annealer.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/8d682d4e9dae59e6df5ec2108039d88e5c4b9629

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum annealing for industry applications: introduction and review (2021, positive): “Cai et al [28] proposed a heuristic algorithm for finding a minor embedding G emb of graph G to the hardware topology graph U that is practical for sparse U and G with hundreds of vertices.”
Experimental investigation of performance differences between coherent Ising machines and a quantum annealer (2018, methodology): “However, all the nonphotonic analog optimization systems realized to date suffer from limited connectivity so that actual problems must, in general, first be embedded (20, 21) into the solver architecture native graph before they can be solved.”
Quantum Optimization of Fully-Connected Spin Glasses (2014, background): “minimizing the number of required nodes) graph minor is itself NP-hard [25] and is typically tackled with heuristic approaches [26], for many graphs with a regular struture an efficient embedding can be found systematically.”