Número de vértices presentes en todas las coincidencias máximas.

Dado un gráfico , necesitamos encontrar la cardinalidad del conjunto más grande de vértices para que cada uno de ellos esté presente en cada coincidencia máxima posible. $G$

¿Hay una solución al lado de lo obvio para eliminar cada vértice y encontrar la coincidencia máxima para ver que se reduce?

graph-theory graph-algorithms Hououin Kyouma
fuente

No veo cómo lo que sugirió es incluso una solución.

$\:$ (Considere un triángulo).

$\hspace{1.4 in}$

@RickyDemer primero encontramos la coincidencia máxima en todo el gráfico. Luego, eliminamos un vértice y encontramos la coincidencia máxima nuevamente. Si la diferencia es 1, entonces podemos decir que este vértice está presente en todas las coincidencias máximas.

evil999man

¿Debería reemplazarse "buscar coincidencia máxima" por "encontrar una coincidencia máxima" o "encontrar todas las coincidencias máximas"?

$\;$

Creo que debería reemplazarse por el tamaño de coincidencia máxima.

evil999man

@ Awesome tiene razón. Editaré mi pregunta.

Hououin Kyouma

Respuestas:

$O(n^3)$

Thomas Kalinowski
fuente

Solo necesito tamaño, no los vértices en sí. ¿Se puede hacer esto en O (n ^ 2)? Y gracias por el artículo

Hououin Kyouma

$v$

Al realizar dos búsquedas de amplitud o profundidad, una para encontrar las partes del gráfico a las que se puede llegar desde vértices no coincidentes y otra para encontrar las partes que pueden alcanzar vértices no coincidentes, puede encontrar los vértices esenciales en tiempo lineal una vez que Ya tengo la coincidencia.

Probablemente, algo como esto también funcionará para el caso no bipartito, utilizando una búsqueda de ruta alterna de contracción en flor, pero los detalles serán más complicados.

David Eppstein
fuente

Tengo curiosidad por cómo lo haría en un gráfico general. ¿Podrías explicarlo?

evil999man

Si ya lo hubiera resuelto en detalle, lo habría incluido en mi respuesta. Pero básicamente solo desea encontrar los vértices a los que se puede llegar alternando caminos desde vértices no alcanzados, ya que esos son los que posiblemente no se puedan igualar. La búsqueda de ruta alterna debería ser más o menos la misma que usas para encontrar la coincidencia en primer lugar.

David Eppstein

Perdón por el comentario tardío. Mi gráfica es general. Trataré de pensar en el método

Hououin Kyouma