min_maximal_matching(G, sampler=None, **sampler_args)[source]

Returns an approximate minimum maximal matching.

Defines a QUBO with ground states corresponding to a minimum maximal matching and uses the sampler to sample from it.

A matching is a subset of edges in which no node occurs more than once. A maximal matching is one in which no edges from G can be added without violating the matching rule. A minimum maximal matching is the smallest maximal matching for G.

  • G (NetworkX graph) – The graph on which to find a minimum maximal matching.
  • sampler – A binary quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Unconstrained Binary Optimization Problem (QUBO). A sampler is expected to have a ‘sample_qubo’ and ‘sample_ising’ method. A sampler is expected to return an iterable of samples, in order of increasing energy. If no sampler is provided, one must be provided using the set_default_sampler function.
  • sampler_args – Additional keyword parameters are passed to the sampler.

matching – A minimum maximal matching of the graph.

Return type:



This example uses a sampler from dimod to find a minimum maximal matching for a Chimera unit cell.

>>> import dimod
>>> sampler = dimod.ExactSolver()
>>> G = dnx.chimera_graph(1, 1, 4)
>>> matching = dnx.min_maximal_matching(G, sampler)


Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.


Matching on Wikipedia

QUBO on Wikipedia

[AL]Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, Volume 2, Article 5.