12
$\begingroup$

Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible.

Is there a solution beside the obvious remove each vertex and find the maximum matching to see it reduces?

$\endgroup$
  • $\begingroup$ I don't see how what you suggested is even a solution. $\:$ (Consider a triangle.) $\hspace{1.4 in}$ $\endgroup$ – user6973 Jul 5 '15 at 17:00
  • 1
    $\begingroup$ @RickyDemer first we find maximum matching in whole graph. Then, we remove a vertex and find maximum matching again. If the difference is 1 then we can say that this vertex is present in all maximum matchings. $\endgroup$ – evil999man Jul 5 '15 at 17:03
  • $\begingroup$ Should "find maximum matching" be replaced with "find a maximum matching" or "find all maximum matchings"? $\;$ $\endgroup$ – user6973 Jul 5 '15 at 17:05
  • $\begingroup$ I think it should be replaced with size of maximum matching. $\endgroup$ – evil999man Jul 5 '15 at 17:06
  • $\begingroup$ @Awesome is right. I will edit my question. $\endgroup$ – Hououin Kyouma Jul 5 '15 at 17:08
11
$\begingroup$

I think you want the Edmonds-Gallai decomposition of your graph which can be computed in time $O(n^3)$ (see these notes).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I need only size, not the vertices themselves. Can this be done in O(n^2) ? And thanks for the paper $\endgroup$ – Hououin Kyouma Jul 7 '15 at 9:14
11
$\begingroup$

Is your graph bipartite? Because, if it is: suppose that one side of the bipartition is left and the other is right. Find a maximum matching, and orient all matched edges left-to-right and all unmatched edges right-to-left. Then a vertex $v$ can be omitted from a maximum matching if and only if one of the three following (mutually exclusive) conditions holds:

  • $v$ is already unmatched
  • $v$ can be reached from an unmatched vertex on its side of the bipartition in the resulting digraph
  • $v$ can reach an unmatched vertex on its side of the bipartition in the resulting digraph.

By doing two breadth-first or depth-first searches, one to find the parts of the graph that can be reached from unmatched vertices and one to find the parts that can reach unmatched vertices, you can find the essential vertices in linear time once you already have the matching.

Probably something like this will also work for the non-bipartite case, using a blossom-contracting alternating path search, but the details will be more complicated.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I am curious how would you do it in a general graph. Could you explain it? $\endgroup$ – evil999man Jul 5 '15 at 21:15
  • $\begingroup$ If I had worked it out in detail already, I would have included it in my answer. But basically you just want to find the vertices that can be reached by alternating paths from unreached vertices, as those are the ones that could possibly be left unmatched. The alternating path search should be pretty much the same as the one you use to find the matching in the first place. $\endgroup$ – David Eppstein Jul 6 '15 at 0:52
  • $\begingroup$ Sorry for late comment. My graph is general. I will try to think through the method $\endgroup$ – Hououin Kyouma Jul 7 '15 at 9:09

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.