clique_emebdding fails where minorminer succeeds

[JoelPasvolsky]

Description pegasus.clique_emebdding fails to embed a K5 in a K_44 cell.

To Reproduce

import dwave_networkx as dnx
from dwave.embedding import *
P1 = dnx.pegasus_graph(2, node_list=[4, 5, 6, 7, 40, 41, 42, 43])

embedding = pegasus.find_clique_embedding(5, target_graph=P1)

returns ValueError: No clique embedding found

k5 = nx.complete_graph(5)
embedding = minorminer.find_embedding(k5, P1.edges)

finds the embedding.

Expected behavior Clique embedding should succeed too.

Environment:

• OS: WIN/UNIX
• Python version: 3.6.5

Additional context

[arcondello]

I believe this is expected behavior. If we were being more verbose, the find_clique_embedding function should be more correctly named find_regular_clique_embedding - embeddings that have all equal chain length. The result is that minorminer, by relaxing the equal chain length requirement, can find embeddings that the clique embedding function cannot.

Additional Context I recall that in Pegasus, regular might actually mean "nearly equal", but I don't remember the rules. @boothby can comment further.

[boothby]

The "clique embedder" searches for cliques of a very specific structural description, in a Chimera graph. We exploit that structural description to produce a polynomial-time algorithm which is effective at "solving" an otherwise NP-Hard problem.

The K_5 you're looking for does not fit into that structural description. In general, I have an unpublished description of a K_{4n+1} into a C_n with nearly-uniform chainlengths -- a similar algorithm exists to find those embeddings, but implementing it is currently a lot of effort compared to the actual payoff (e.g. it is very rare that masks contain few enough defects to yield that embedding).

I would recommend against putting a bunch of effort into testing this code, as it's soon going to be replaced wholesale.

[JoelPasvolsky]

Thanks @boothby and @arcondello. I was not testing, I was naively using: the description does not include the details now explained.

Given a clique (fully connected graph) and target Pegasus graph, attempts to find an embedding by transforming the Pegasus graph into a K2,2 Chimera graph and then applying a Chimera clique-finding algorithm. Results are converted back to Pegasus coordinates.

This issue can be used to update the description if the limitations will still apply to the new code. Thanks!

[boothby]

That's a great description, thank you.

[arcondello]

I believe this is resolved.