# An example where the algorithm of Hopcroft and Karp performs poorly?

I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $$\Omega(\log n)$$ rounds). However, all the examples I came up with where solved on paper in almost constant number of rounds.

Other questions here in the community targeting this problem tackle the worst-case running time or the time-bound proven in the original paper.

This running time seems to be a bit too loose, especially because the maximum matching problem in general and in bipartite graphs lacks a conditional lower-bound on its running time and I couldn't find any tight lower-bound on the number of needed rounds. I couldn't find a bound on the number of needed operations in constrained models of computing either (For example binary decision tree or so).

On the other side, the $$O(\sqrt n)$$ bound on the number of rounds from the original paper has not been improved since was found in the 1973 except in the parameterized context and in special classes of graphs.

Any ideas/suggestions are much appreciated :)

I was able to construct a simple example where the algorithm taken literally is easy to trick. The case goes as follows. Given a bipartite graph consisting of a union of simple paths of odd lengths $$P_1, P_3, P_5, \dots, P_{2r-1}$$ for some $$r \in \mathbb{N}$$. Assuming $$P_i = v_{i,0}, v_{i,1} \dots v_{i,i}$$ for $$i = 2k-1; k \in [r]$$. The shortest augmenting path in the first iteration has length one (namely any edge in the graph is such a path). Consider the following scenario of the algorithm.
In the first iteration, the algorithm chooses $$\left\lfloor \frac{i}{2} \right\rfloor$$ edges from each path $$P_i$$, namely the edges $$v_{i, 2}, v_{i, 4}, \dots v_{i, i-1}$$ as a maximal set of shortest augmenting paths. The set is maximal, since any other edge share an endpoint with an edge in the set. However, the matching resulting from these edges admits an augmenting path in each path $$P_i$$ of the length $$i$$. Since all paths have distinct lengths, the algorithm as given in the paper from Hopcroft and Karp augment exactly one path in each phase (in the pahse $$j$$ it will not look for paths longer than $$2j-1$$ since an augmenting path of this length exists). In total we need $$\Omega(r)$$ phases which is $$\Omega(\sqrt n)$$ with simple math. This bound is tight to the proven bound.