Other algorithms needed: FAST, Bandwidth with counting


Check that max degree is less than 2k+1, and break into connected components.

L_0 = list of all ordered sets of k vertices, and their dangling edges.

for i =1 to n-k do

\\ Create L_i, the list of all configurations that imply a prefix of size i.

for j =1 to length(L_{i-1}) do

\\ add to L_i all of the legitimate configurations which can come from L_{i-1}(j)

C = L_{i-1}(j);

Let x be the left-most vertex of the active region of C.

If x has more than one dangling edge, don't add anything to L_i

If x has exactly one dangling edge <x,y>,

Add update(C,y) to L_i

If x has no dangling edges

For v \in suffix(C)

Add Update(C,v) to L_i

If L_{n-k} is non-empty, return 'yes'. Otherwise, return 'no'

Procedure GetConfig(prefix, active, suffix)

\\ returns a configuration which implies the input.

The configuration is active and all edges from active to suffix.

Procedure prefix(C)

Remove all dangling edges from G

For each vertex in the active region

Do a DFS and add all vertices found which aren't in the active region to the prefix

Return prefix

Procedure suffix(C)

return V-prefix(C)-active(C)

Procedure Update(C, y \in suffix(C))

new_active = active(C)-x


new_prefix = prefix(C)+x

new_suffix = suffix(C)-y

return GetConfig(new_prefix, new_active, new_suffix)