0
$\begingroup$

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: A poorly-drawn example.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Feb 11 '21 at 18:36
  • $\begingroup$ @MatthieuLatapy Thanks for your suggestion. I have posted this question there too $\endgroup$
    – jadball
    Feb 11 '21 at 18:59
  • $\begingroup$ 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... $\endgroup$
    – Will Sawin
    Feb 12 '21 at 0:37
  • $\begingroup$ Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Feb 12 '21 at 3:40
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.