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?