SM-3f-TestingForClawsII:ElectricBoogaloo

4136 days ago by MathFest

In this worksheet we'll implement an algorithm which can be used to determine, for a given tree $T$, the number $c(T)$ such that $T^k$ is claw-free if and only if $k \geq c(T)$. (The algorithm developed below appears in a recently completely manuscript on generalized independence polynomials.) The first step is to reproduce a fairly elementary method, one which finds all subsets of a given set of a given size:
def subset_size_n(L,n): pow = list(powerset(L)) sets = [] for s in pow: if len(s) == n: sets.append(s) return sets 
       
The next method, a more graph theoretical one, finds the leaves of a tree $T$ which is input as an adjacency matrix. This simple procedure runs in time $O(n)$, where $n$ is the order of the tree $T$.
def find_leaves(m): leaves = [] for i in [0..len(m.rows())-1]: if sum(m.rows()[i]) == 1: leaves.append(i) return leaves 
       
Now for the trickiest step: to compute the distance matrix for $T$, we put together a method which returns a list of the spheres of various radii $1,2,...,{\rm diam}(T)$, centered at a given vertex of $T$. The running time of this procedure if $O(n)$ as well, and we will end up calling it $O(\ell)$ times, when $T$ has $\ell$ leaves.
def find_spheres(m,basept): dim = len(m.rows())-1 vertex_count = 1 rad = 1 spheres = [[basept]] while vertex_count < dim: new_sphere = [] if rad == 1: for j in [0..dim]: if m.rows()[basept][j] == 1: new_sphere.append(j) vertex_count = vertex_count+1 else: for i in spheres[rad-1]: for j in [0..dim]: if m.rows()[i][j] == 1 and not j in spheres[rad-2] and not j in new_sphere: new_sphere.append(j) vertex_count = vertex_count+1 spheres.append(new_sphere) rad = rad + 1 return spheres 
       
Finally, we call the previous method on each leaf, and from the information contained in the resulting output we reconstruct the distance matrix, restricted to the set of $T$'s leaves:
def find_leaf_distances(m,L): dim = len(m.rows())-1 d = [[0 for i in [0..dim]] for j in [0..dim]] leaf_spheres = [find_spheres(m,L[i]) for i in [0..len(L)-1]] for i in [0..len(L)-1]: for j in [0..len(leaf_spheres[i])-1]: for k in leaf_spheres[i][j]: if k in L: d[L[i]][k] = j d[k][L[i]] = j return d 
       
All right...now all we have to do to find the value $c(T)$ described above is find, for each triple $\{\ell_1,\ell_2,\ell_3\}$ of leaves, the smallest distance $\rho(\ell_i,\ell_j)$, and take the maximum over all leaf triples of this value. This stage of the algorithm runs in time $O(\ell^3)$:
def find_c(d,L): if len(L) == 2: return False else: trios = subset_size_n(L,3) return max([min([d[t[0]][t[1]],d[t[0]][t[2]],d[t[1]][t[2]]]) for t in trios]) 
       
Let's take it for a test drive!:
G = graphs.RandomBarabasiAlbert(25,1) show(G) m = matrix(G) print m L = find_leaves(m) print L c = find_c(find_leaf_distances(m,L),L) print c