2
$\begingroup$

(this is a cross-post from mathoverflow)

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$
15
  • 1
    $\begingroup$ If the cycle doesn't have to be simple, then yes, you can solve this using dynamic programming (If the cycle must be simple, then it's NP-hard, by reduction from Hamiltonian cycle). The state consists of $3$ things: 1) starting vertex 2) current vertex 3) current position in $c$. Intuitively, you build a path starting from some vertex, and you need to close the path at the same vertex. $\endgroup$
    – user114966
    Feb 11 at 20:32
  • $\begingroup$ The natural heuristic is to pick an edge $e$ on the cycle, and go over all edges in the graph having the same weight; for each such edge $e'$, try to match a neighbor of $e'$ with a neighbor of $e$, and so on. A similar algorithm is used in color coding. $\endgroup$ Feb 11 at 20:52
  • $\begingroup$ Are the weights on your cycle distinct? Are the weights adjacent to each vertex in the graph distinct? $\endgroup$ Feb 11 at 20:52
  • 1
    $\begingroup$ So you are interested only in cycles of length 3? Why not just try all triples of vertices? There are $O(n^3)$ of them. $\endgroup$
    – user114966
    Feb 11 at 23:01
  • 1
    $\begingroup$ Try it. It should be really fast. To begin with, in the worst case it should take about a second. If the data is not adversarial, then you can skip a lot of triples (if $d(v_1, v_2) \ne c_1$, which will happen in a lot of cases, you don't even have to consider $v_3$). You could add other optimizations, e.g. for $v_1$ find all possible $v_2$ and $v_3$ candidates in advance, then iterate over the smallest set of candidates; assuming that you've selected $v_2$, then, again, you can find $v_3$ by iterating over the smallest set of candidates. $\endgroup$
    – user114966
    Feb 11 at 23:58
1
$\begingroup$

Welcome to CS.SE.

I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy.

A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right?

This leads to the following python 2.7 code, that does not make the assumption that the graph is complete. Its core is the find function, everything else is for playing and testing.

import random
random.seed()

min_weight,max_weight=1,20
c_length=30

# build the graph (complete in this case)
V = ['A','B','C','D','E']
N = {u:[v for v in V if v!=u] for u in V}
weight = {}
for (u,v) in [(u,v) for u in V for v in N[u] if u<v]:
        weight[(u,v)] = weight[(v,u)] = random.randint(min_weight,max_weight)
for (u,v) in sorted(weight):
        print u+'--'+str(weight[(u,v)])+"--"+v

# build a correct sequence of weights
c = []
u = random.choice(V)
while len(c)<c_length:
        v = random.choice(N[u])
        c.append(weight[(u,v)])
        u = v
print c

# search all paths corresponding to the weight sequence in the graph
def find(c,S):
        if len(c)==0:
                return(S)
        return set([u+r for u in S for r in find(c[1:],[v for v in N[u] if weight[(u,v)]==c[0]])])

result = find(c,V)
print result

# check results
def check(x):
        if len(x) != len(c)+1:
                return(False)
        for i in xrange(len(x)-1):
                if weight[(x[i],x[i+1])] != c[i]:
                        return(False)
        return(True)
for x in result:
        assert(check(x))

Is it correct? It is far from optimal, of course.

$\endgroup$
3
  • $\begingroup$ Thank you for your reply. I tried this code out and it has one problem (because I didn't define this properly) - each edge should only be traversed once. Therefore, for a length-3 weight sequence, we would be finding complete triangles only. $\endgroup$
    – jadball
    Feb 11 at 21:59
  • $\begingroup$ Oh, I think this makes the problem seriously more difficult, doesn't it? Still, it is easy to patch my code for it, by avoiding using an already used edge in the recursive call. But the running time may be awful. $\endgroup$ Feb 11 at 22:20
  • $\begingroup$ I am only interested in cycles of length 3. As your program returns 4-length strings in that case, I can just check that the first and last letters are the same (e.g ABCA would work, but ABCB wouldn't work). $\endgroup$
    – jadball
    Feb 11 at 22:28
1
$\begingroup$

This answers a different question: a cycle is not necessarily simple.

You can use the following dynamic programming solution:

fun dfs(v, start_v, c_pos, visited_vertices):
    if c_pos = c.length then
        // Used all edges
        if v = start_v then
            // Returned to the starting vertex
            visited_vertices is the answer for the problem
    else
        if was[v, start_v, c_pos] then
            // We've already been in this state and didn't find an answer
            return 
        was[v, start_v, c_pos] <- true
        for each vertex u such that d(v,u) = c[c_pos] do
            // u is a possible next vertex on the path
            dfs(u, start_v, c_pos + 1, visited_vertices + [u])

set all was[u, v, pos] to false

for each vertex v do
    dfs(v, v, 0, [v])

The core is the dfs function: we've started a path at vertex start_v, visited vertices visited_vertices and currently stay at vertex v. During this, we've used weights c[0], ..., c[c_pos - 1] from the list c. (Note that v, start_v and c_pos are actually redundant since they can be recovered from visited_vertices, but I left them for clarity).

If c_pos = c.length, then we've used the entire list c. If we've returned to the original vertex (i.e. v = start_v), then we've found the required cycle.

Otherwise, the function tries to find the next edge in the path. It simply tries all next vertices u (such that d(u,v) matches the next expected length) and runs dfs from them. The main optimization is dynamic programming. If we've already been in some state and didn't find an answer, then we abandon the current path. Note that visited_vertices doesn't matter for the state (since visited vertices don't affect whether we can find the rest of the path): we only care about starting vertex, current vertex, and the number of used edges.

Therefore, the total running time is $O(n^3 \cdot c.length)$: there are $O(n^2 \cdot c.length)$ states, and for each state we need $O(n)$ time.

$\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.