4
$\begingroup$

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 :)

$\endgroup$
0
$\begingroup$

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.

I considered this case trivial, since all augmenting paths are vertex disjoint and instead of looking for maximal set of vertex-disjoint shortest augmenting paths in each phase, we can look for a maximal set of vertex-disjoint augmenting paths with monoton-increasing lengths of the paths. I mean with that, that in each phase, after we run the BFS, we do not stop when a maximal set of vertex disjoint shortest augmenting paths are found, but we look further for (second-shortest) augmenting paths that are vertex-disjoint from what we already found and so on. In this case we would have considered all augmenting paths in the given graph in the previous example in one step.

On the other hand, it is not directly clear how to implement this kind of rounds in linear or almost-linear time from the given implementation of the algorithm in the paper of Hopcroft and Karp.

I was able to go further and construct examples with a bit more complicated structures and the same number of rounds, where we add edges arbitrarily between the middles of these given simple paths or parallel copies of subpaths. Even though, these edges might change the sequence of the algorithm, since they can be chosen at the first round of the algorithm, it is not hard to see that the total number of rounds does not change critically.

On the other hand, dense graphs seem to need less rounds in general. This can also be seen "intuitively" from results proben by Hegerfeld and Kratsch in this paper, which gives more insight about the number of needed rounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.