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$
5
  • $\begingroup$ I don't see how what you suggested is even a solution. $\:$ (Consider a triangle.) $\hspace{1.4 in}$ $\endgroup$
    – user6973
    Jul 5, 2015 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, 2015 at 17:03
  • $\begingroup$ Should "find maximum matching" be replaced with "find a maximum matching" or "find all maximum matchings"? $\;$ $\endgroup$
    – user6973
    Jul 5, 2015 at 17:05
  • $\begingroup$ I think it should be replaced with size of maximum matching. $\endgroup$
    – evil999man
    Jul 5, 2015 at 17:06
  • $\begingroup$ @Awesome is right. I will edit my question. $\endgroup$ Jul 5, 2015 at 17:08

2 Answers 2

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

$\endgroup$
1
  • $\begingroup$ I need only size, not the vertices themselves. Can this be done in O(n^2) ? And thanks for the paper $\endgroup$ Jul 7, 2015 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.

$\endgroup$
3
  • $\begingroup$ I am curious how would you do it in a general graph. Could you explain it? $\endgroup$
    – evil999man
    Jul 5, 2015 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$ Jul 6, 2015 at 0:52
  • $\begingroup$ Sorry for late comment. My graph is general. I will try to think through the method $\endgroup$ Jul 7, 2015 at 9:09

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.