2
$\begingroup$

I have a simple question which I cannot answer, and it relates to this question.

What I cannot answer is this:

  1. Why does a graph with bidirectional edges destroy the "bipartiteness" of the graph?
  2. Depending on the answer to question 1, why wouldn't Hopcroft-Karp work on bidirectional graphs?

Specifically, for question 1, it seems we can do the following:

  1. Assume that a graph with bidirectional edges with node set $A$ with cardinality $|A|$ is actually two sets of nodes $B, C$, each with cardinality equivalent to $|A|$ such that $|B \cup C| = 2 |A|$ and there is guaranteed to be an edge from $B \rightarrow C$ if there is an edge from $C \rightarrow B$.
  2. This would be analogous to the stable marriage problem, where every time a marriage is desired in one direction, it is reciprocated. It seems like an unlikely but valid setup.

Is there a problem with viewing a bipartite graph in this way? It seems like a valid setup to me.

$\endgroup$

1 Answer 1

4
$\begingroup$

I don't see why bi-directional edges are relevant here (or what problem your construction tries to solve), the question you reference is only about undirected graphs. But I can understand your confusion with that Q&A pair. My understanding is that:

  1. The questioner wants to match the entries of an array $A$ to other entries of this array, where the edges are given due to some condition, and try to do so by making a copy $B$ of $A$, and create a bipartite graph on them. However, they note that then they need the additional requirement that if $(A[i],B[j])$, are matched then $(A[j],B[i])$ must also be matched
  2. The answer notes that they should not try to make a bipartite graph. What they mean is that the additional constraint on the bipartite graph corresponds to the original edge-relation on the array $A$. As the original edges were arbitrary, we need to perform matching on a general undirected graph.

The standard formulation of the Hopcroft-Karp algorithm uses the fact that the graph is bipartite to ensure finding augmenting paths is not too difficult. It is apparently possible to extend this procedure efficiently for general undirected graphs, but this is rather complicated, so using another algorithm such as Edmonds algorithm seems a better choice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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