Número de vértices presentes em todas as correspondências máximas

Dado um gráfico , precisamos encontrar a cardinalidade do maior conjunto de vértices para que cada um deles esteja presente em todas as correspondências máximas possíveis.$G$

Existe uma solução ao lado do óbvio remover cada vértice e encontrar a correspondência máxima para ver que ela reduz?

$O(n^3)$

$v$

• $v$
• $v$
• $v$

Ao fazer duas pesquisas de amplitude ou profundidade, uma para encontrar as partes do gráfico que podem ser alcançadas a partir de vértices não correspondentes e a outra para encontrar as partes que podem alcançar vértices sem correspondência, você pode encontrar os vértices essenciais em tempo linear, depois de já tem a correspondência.

Provavelmente algo assim também funcionará para o caso não bipartido, usando uma pesquisa de caminho alternativo que contrai a flor, mas os detalhes serão mais complicados.