# Worst-case sparse graphs for Hopcroft-Karp Algorithm

Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and architecture, and why does it cause a problem?

Further, in many implementations the DFS part is implemented using recursion, eg from Wikipedia:

function DFS (v)
if v != NIL
for each u in Adj[v]
if Dist[ Pair_G2[u] ] == Dist[v] + 1
if DFS(Pair_G2[u]) == true
Pair_G2[u] = v
Pair_G1[v] = u
return true
Dist[v] = ∞
return false
return true


What is the approximate maximum depth of the recursion in the worst case?

• The maximum recursion depth of DFS is $n$; the DFS tree might consist of a single (Hamiltonian) path. – JeffE Aug 8 '12 at 21:48