Proving a recursive algorithm

Question

I need to prove a recursive algorithm. Normally this would be done using some integer value within the code as the base case for induction like when computing a factorial but with a graph traversal I have no idea where to begin. Here is my algorithm. Subscripts didn't convert.

Algorithm

Goal: Traverse a graph creating a depth-first spanning tree, and compute the Last descendent of each vertex that is the descendent vk that has the highest value of k

Input: A connected graph G with vertices ordered v1, v2, v3 … vn

Output: A spanning tree T where each vertex in T has had its Last vertex computed

Initialization Set each vertex to unvisited. Let ak denote a list of all vertices adjacent to vk. Let lk denote the Last descendent of vk. Let ck denote the list of all the children of vk in the spanning tree. Let dk denote the list of all vertices that are descendents of vk in the spanning tree including vk.

dfs(vk){

    add vK to T
    set v to visited
    lk = vk
    add vk to dk
    foreach(vertex m in ak with lowest value of k){
        add m to ck
        add dfs(m) to dk
    }
    foreach(vertex vc in dk){
        if( c > k){
            lk = vc
        }
    }
    if(k = 1)
        return T
    else
        return dk
}

This is for a group project at school so I don't want the whole proof but a starting point and some direction would be greatly appreciated.

Answer 1

I'm having a hard time understanding your pseudo code. It seems unclear at best, probably the algorithm doesn't even work. Some issues:

• The "visited" property is set, but never used.
• T is supposed to be a tree. But you only ever add vertices, no edges to it. Without edges, it's certainly not a spanning tree. If you consider all edges from the original graph between the nodes in T part of T, then it will contain cycles and won't be a tree, either.
• Why do you calculate lk, if it's never used?
• Is the parameter of your function dfs supposed to be k instead of vk? Otherwise k is never set, but it is being used.
• I fail to see how your recursion ever terminates. I don't see any guards for the base case (except for maybe the "with lowest value of k" condition in your loop - which I don't understand because I understand from the rest of the code that k is the input parameter of the function and therefore m doesn't depend on it).

So let me tell you about proving recursive algorithms over graphs in general. Apart from the induction over natural numbers that you mentioned, there is also Structural Induction. It has a base case and an inductive step, just like the induction you know. But the base case is usually a trivial component of your data structure and the inductive step proves your proposition for more complex composites, assuming that your proposition holds for its less complex components.

For example, you can prove an algorithm over trees by proving that it works for the leafs (your base case) and by proving that it works for a whole tree, assuming that your algorithm works for the left and right sub-trees of the root (induction step).

Since your graph, other than the tree example above, may contain cycles, it's not automatically guaranteed that the data structure that is passed to your recursive call is less complex than the original one. But your algorithm probably has some way to ensure that the recursive call takes into account only a part of the graph, probably via the "visited" flag. In that case the recursive call has to take into account only the "not visited" subgraph. So you can induce over those unvisited subgraphs. Start from the base case with only one vertex being unvisited. And then inductively add one unvisited node (including its edges) to the unvisited subgraph.