<p>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:</p>

<ul>
<li>$v$ is already unmatched</li>
<li>$v$ can be reached from an unmatched vertex on its side of the bipartition in the resulting digraph</li>
<li>$v$ can reach an unmatched vertex on its side of the bipartition in the resulting digraph.</li>
</ul>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-07-05T21:15:17.433Z
I am curious how would you do it in a general graph. Could you explain it?
evil999man
CC BY-SA 3.0
2015-07-06T00:52:33.237Z
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.
David Eppstein
CC BY-SA 3.0
2015-07-07T09:09:49.563Z
Sorry for late comment. My graph is general. I will try to think through the method
Hououin Kyouma
CC BY-SA 3.0
2015-07-05T20:53:48.757Z
2016-03-19T17:34:52.587Z
2016-03-19T17:34:52.587Z
David Eppstein
<p>I think you want the Edmonds-Gallai decomposition of your graph which can be computed in time $O(n^3)$ (see <a href="https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture8.pdf">these notes</a>).</p>

CC BY-SA 3.0
2015-07-07T09:14:10.070Z
I need only size, not the vertices themselves. Can this be done in O(n^2) ? And thanks for the paper
Hououin Kyouma
CC BY-SA 3.0
2015-07-05T23:16:33.407Z
2015-07-05T23:16:33.407Z
Thomas Kalinowski
<p>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. </p>

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

CC BY-SA 3.0
2015-07-05T17:03:39.660Z
@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.
evil999man
CC BY-SA 3.0
2015-07-05T17:06:24.810Z
I think it should be replaced with size of maximum matching.
evil999man
CC BY-SA 3.0
2015-07-05T17:08:46.757Z
@Awesome is right. I will edit my question.
Hououin Kyouma
<graph-theory><graph-algorithms>
Number of vertices present in all maximum matchings
Hououin Kyouma
# Number of vertices present in all maximum matchings

(Asked by: username_0 on 2015-07-05)

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?

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: @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.  
> **username_1**: I think it should be replaced with size of maximum matching.  
> **username_0**: @Awesome is right. I will edit my question.  

---

## 2 answers

### Answer by username_2 on 2015-07-05. Score: 11

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.

> **Comments:**
> **username_1**: I am curious how would you do it in a general graph. Could you explain it?  
> **username_2**: 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.  
> **username_0**: Sorry for late comment. My graph is general. I will try to think through the method  

---

### Answer by username_3 on 2015-07-05. Score: 11

I think you want the Edmonds-Gallai decomposition of your graph which can be computed in time $O(n^3)$ (see [these notes](https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture8.pdf)).

> **Comments:**
> **username_0**: I need only size, not the vertices themselves. Can this be done in O(n^2) ? And thanks for the paper  

---

