dwave_networkx.algorithms.matching.min_maximal_matching#

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.

Parameters:

  • 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.

Returns:

matching – A minimum maximal matching of the graph.

Return type:

set

Example

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)

Notes

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

References

Matching on Wikipedia

QUBO on Wikipedia

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