# Find cycles with specific weights in complete graph

Assume I have an undirected edge-weighted complete graph $$G$$ of $$N$$ nodes (every node is connected to every other node, and each edge has an associated weight). Assume that each node has a unique identifier.
Let's say I then have an input, $$c$$ of three edges (e.g $$c=[4,7,6]$$). Does an algorithm exist that lets me search $$G$$ for instances of $$c$$, and returns the identifiers of the matching nodes?
The cycles it returns must be closed loops, such as $$[A, D, B, \text{(then back to A)}]$$, rather than $$[D, A, B, A]$$

Here is a poorly-drawn example: .

• Welcome to MO. I fear your question does not fit the scope of this site, but I am pretty sure you would have good answers if you post it to cs.se: cs.stackexchange.com Feb 11 '21 at 18:36
• @MatthieuLatapy Thanks for your suggestion. I have posted this question there too Feb 11 '21 at 18:59
• When you cross-post to different stack-exchange websites, you should link both ways, so that people on each sites can see what people on the other site might have done... Feb 12 '21 at 0:37
• – D.W.
Feb 12 '21 at 3:40

You can form for each weight a matrix with $$1$$s for edges of that weight and $$0$$s elsewhere, and then multiply the matrices. The location of a nonvanishing diagonal entry will tell you the first vertex of your cycle. Then use partial products to succesively find the remaining vertices - if $$i$$ is the first vertex $$M$$ is the product of the first $$j$$ matrices, and $$N$$ is the product of the last $$k-j$$ matrices, then the $$j+1$$st element of the cycle should be an $$l$$ such that $$M_{il}\neq 0$$ and $$N_{li} \neq 0$$.
This takes time $$O( k \cdot n^{\omega+\epsilon})$$ where $$k$$ is the length of the cycle, $$n$$ is the number of vertices, and $$\omega$$ is the matrix multiplication constant, as long as we store partial matrix products so we don't have to compute them.
A trivial lower bound is $$n^2$$ (you might have to check most of the edges to find the cycle) so this is pretty close, at least when $$k$$ is small.