Source-linked AI summary
A practical heuristic for finding graph minors
Jun Cai, William G. Macready, Aidan Roy
TL;DR
The paper addresses the NP-hard problem of finding an H-minor in G when both graphs are inputs, motivated by mapping quadratic pseudo-Boolean optimization onto quantum-annealing hardware. It presents a heuristic that is practical for sparse graphs with hundreds of vertices, while also identifying performance trade-offs and useful outputs when embedding fails.
Problem
When both H and G are inputs, finding whether G contains H as a minor is NP-hard, despite its importance for mapping optimization problems onto quantum-annealing hardware.
Method
The paper presents a heuristic minor-embedding algorithm that represents logical vertices by connected subgraphs of physical qubits and seeks embeddings with low physical-qubit usage.
Results
The implemented algorithm has proven effective for finding minors in sparse G and H with hundreds of vertices, and failed embeddings still produce G-decompositions that may support Ising-model algorithms.
Takeaways & Limitations
Better minor-finding algorithms can directly improve the use of D-Wave quantum annealing for quadratic pseudo-Boolean optimization problems.
Takeaways & Limitations
The algorithm may be substantially improvable through better initial choices for vertex models, making initial placement a future-work challenge.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper motivates heuristic minor-embedding because exact algorithms are impractical when both graphs are inputs, while minor-embedding supports optimization on D-Wave hardware.
- Motivation: When both H and G are inputs, minor-embedding is NP-hard, and exact algorithms are impractical beyond tens of vertices.Existing general algorithms are non-constructive and have prohibitively large constant factors.
- Heuristic approach: Heuristic minor-embedding finds a minor with some probability without exhaustive search or proving minor-exclusion after failure.The approach targets practical discovery rather than an exact decision procedure.
- Related work: Heuristic minor-embedding for arbitrary H has received little attention in graph theory, possibly because applications were not known.The paper connects this underexplored problem to a practical quantum-annealing application.
- Application: Minor-embedding is central to mapping quadratic boolean optimization problems onto D-Wave hardware because the problem graph must be a minor of the hardware graph.The paper develops this application in a later section.
2 Minor-embedding and quantum annealing
D-Wave represents optimization variables through connected collections of physical qubits, so mapping an Ising model requires a minor-embedding into the hardware interaction graph.
- Quantum annealing: D-Wave’s Ising model minimizes a quadratic energy over boolean variables represented by qubits.The workflow expresses an optimization problem with boolean variables, reduces it to quadratic form, and maps it to hardware.
- Minor-embedding: A logical qubit is represented by any connected subgraph of physical qubits, with strong couplings enforcing a shared value.The hardware implementation uses a finite coupling range in practice.
- Minor-embedding: An Ising model can be represented on the hardware if and only if its interaction graph is a minor of the hardware graph.This equivalence makes minor-embedding the central mapping problem.
- Hardware setting: Both G and H must be treated as inputs because disabled qubits alter each processor’s hardware graph and future hardware may use different graphs.Chimera’s large treewidth also makes exact algorithms impractical at current scales.
- Embedding quality: Different embeddings can produce different hardware performance, motivating minimization of either the largest model size or total physical-qubit usage.These are distinct optimization objectives for a given embedding problem.
3 A minor-embedding algorithm
The heuristic constructs connected vertex-models for H using weighted shortest paths in G, then iteratively refines overlaps and model sizes until an embedding is found or progress stops.
- Definitions: An H-minor maps each vertex of H to a connected, pairwise-disjoint vertex-model in G, with edges of H realized by edges between corresponding models.The paper calls φ(x) the vertex-model representing x.
- Vertex-model construction: For a vertex y adjacent to already modeled neighbors, the heuristic seeks a connected model sharing an edge with each neighbor while using few vertices.This preserves room for vertex-models constructed later.
- Vertex-model construction: The root of a new vertex-model is selected by minimizing weighted shortest-path costs to its neighboring models, and the model is the union of corresponding shortest paths.Figure 2 illustrates this root-selection and path-union procedure.
- Overlap handling: When no unused vertex can reach every neighboring model, the heuristic temporarily permits overlaps and chooses a model minimizing the number of multiply represented vertices.Vertex weights grow exponentially with the number of H-vertices represented at a G-vertex.
- Refinement: After initialization, the algorithm repeatedly removes and reinserts models to reduce overlaps, prioritizing the maximum overlap and then total model size.It stops upon finding disjoint models or after a fixed number of iterations without improvement.
Implementation and improvements
Implementation choices accelerate weighted shortest-path computations and resolve path-sharing decisions, while randomized roots help avoid local optima during heuristic search.
- Shortest paths: The implementation supports vertex-weighted shortest paths by translating vertex weights into directed arc weights.Each arc receives the weight of its head, allowing Dijkstra’s algorithm to be used.
- Algorithm interface: The algorithm accepts graph H and graph G, returning vertex-models for an H-minor or failure.The procedure is summarized as findMinorEmbedding(G,H).
- Shortest paths: A dummy vertex adjacent to every vertex-model member computes shortest-path distances to the whole subset efficiently.This avoids separately computing distances to each vertex in a model.
- Path assignment: Shared vertices on multiple shortest paths are assigned to the new model, reducing the number of H-vertices represented at one G-vertex.Vertices appearing on only one path are assigned to the corresponding neighboring model.
- Randomization: Random root selection chooses vertices with probability proportional to e^-cost(g), helping the search avoid local optima.This randomization replaces deterministic minimum-cost root selection as an optional heuristic choice.
4 Running time and performance
The algorithm’s running time is dominated by repeatedly computing shortest-path distances, and its performance was evaluated across several graph families and sizes.
- Shortest-path distance computations dominate the algorithm’s running time and must be recomputed as vertex weights change.The distances are recalculated in every iteration because the set of used vertices changes.
- Each iteration calls Dijkstra 2eH times, with each call taking O(eG + nG log nG).The total number of iterations is bounded by the possible improvements in the sum of vertex-model sizes.
- Performance was measured on complete, grid, and random cubic graphs embedded into the Chimera graph.For each graph type and size, the algorithm was run 100 times while recording runtime and minor-finding success.
5 Localized version
The localized version accelerates shortest-path searches by combining multisource computation with A* guidance, but may trade success probability for speed.
- The modification replaces separate shortest-path computations with a single multisource computation and typically searches locally for vertex-model roots.This avoids exploring the entire graph when a suitable root can be found in a smaller region.
- Multisource Dijkstra selects the currently closest source-frontier vertex and stops when one vertex has been reached by all sources.The selected vertex minimizes the maximum shortest-path distance among the sources.
- Multisource A* uses previous vertex-model roots as targets and precomputed unweighted distances as heuristic estimates.When no vertex-model improvement is possible, the search favors vertices closer to the previous root.
- The A* variant is considerably faster than Dijkstra, but its success probability is sometimes poorer because it considers only the worst overlap.Dijkstra instead minimizes the sum of shortest-path distances and therefore accounts for all overlaps.
6 Summary and future work
The paper presents a heuristic minor-finding algorithm for sparse input graphs with hundreds of vertices and identifies useful failure outputs and future improvements.
- The algorithm targets the setting where both H and G are inputs and has been effective for sparse graphs with hundreds of vertices.The authors describe it as the first heuristic algorithm for this problem to their knowledge.
- Even when minor-finding fails, the algorithm returns a G-decomposition that may help algorithms solving Ising models.A G-decomposition permits multiple vertices of H to share a vertex of G, unlike an H-minor.
- Better initial choices for first-iteration vertex models are identified as a likely source of significant improvement.Developing a heuristic for initial placement is left as future work.