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 trueWhat is the approximate maximum depth of the recursion in the worst case?
Worst-case sparse graphs for Hopcroft-Karp Algorithm
algorithms;graph theory;algorithm analysis;runtime analysis