La coincidencia máxima M con la condición G [M] está libre de 2K_2

11

¿Hay algo en la literatura cercano al siguiente problema:

Dado un gráfico bipartito con bipartición equilibrada , ¿existe una coincidencia perfecta en manera que por cada 2 aristas , exista una arista o arista? (o ambos) en ?{ U , W } M G u 1 w 1 , u 2 w 2M u 1 w 2 u 2 w 1 GG(V,E){U,W}MGu1w1,u2w2Mu1w2u2w1G

En otras palabras, ¿existe una coincidencia perfecta tal que la inducida esté ? (Con bipartición equilibrada, quise decir .)G [ M ] 2 K 2 | U | = | W |MG[M]2K2|U|=|W|

La condición adicional es algo así como un extremo opuesto al que se usa en el problema de coincidencia inducida. Otro posiblemente relacionado es el problema de encontrar el tamaño máximo que coincida con en el gráfico bipartito modo que la contracción de los bordes en minimice el número de bordes que quedan en el gráfico.G MMGM

Revisé la lista de problemas relacionados con la coincidencia dada por Plummer en Emparejamiento y empaque de vértices: ¿qué tan "difíciles" son? sin éxito.

PD: Este problema es un caso especial de este problema de decisión: - Para un determinado , ¿existe una coincidencia máxima de un gráfico bipartito tal que esté y . Si el gráfico de entrada es bipartito equilibrado, obtenemos el problema anterior. M G G [ M ] 2 K 2 | M | > k k = | U |kNMGG[M]2K2|M|>kk=|U|

Gracias.

Antonio cirio
fuente
La coincidencia perfecta puede no ser la palabra correcta. Básicamente estamos preguntando si hay una coincidencia máxima que tenga tamañocon la propiedad mencionada. |U|
Cyriac Antony
En cierto sentido, estamos pidiendo algo opuesto a lo que se llama una fuerte coincidencia. Una coincidente fuerte en un gráfico es una coincidente de tal manera que no haya bordes en conecten dos bordes deG M G MMGMGM
Cyriac Antony
Lo siento, por , me refería al subgrafo de inducido por vértices 'en'G MG[M]GM
Cyriac Antony

Respuestas:

5

¡Sorpresa! (para mi).
Este tipo de coincidencias ya se estudian en la literatura. Se llaman emparejamientos conectados .

Fueron presentados por Plummer, Stiebitz y Toft en su estudio sobre la conjetura de Hadwiger. Vea el capítulo "Emparejamientos conectados" de Cameron en el libro "Optimización combinatoria - ¡Eureka, te encoges!"

El estado de las coincidencias conectadas en gráficos bipartitos (no necesariamente equilibrado) está abierto a mi leal saber y entender (actualizaré ). La versión ponderada del problema es NP-complete para gráficos bipartitos. El problema es el tiempo polinómico solucionable para gráficos bipartitos cordales.

Actualización: el problema es NP-completo para gráficos bipartitos equilibrados (es decir, el problema exacto formulado en la pregunta). Esto se demuestra en el documento " Capacidad multitarea: resultados de dureza y construcciones mejoradas " de Alon et al. También informan que encontrar el tamaño de una coincidencia conectada más grande es difícil de aproximar dentro de un factor de menos que NP = co-RP.n1ϵ

Notas agregadas anteriormente (guardadas para las personas interesadas):
" Emparejamientos conectados en gráficos bipartitos cordales " por Jobson et al. (doi: https://doi.org/10.1016/j.disopt.2014.06.003 ) y " Emparejamientos conectados en familias especiales de gráficos " por Caragianis (tesis) son dos referencias notables.

Antonio cirio
fuente
1

Hay otra forma de hacer esta pregunta. ¿Existe una coincidencia perfecta de un gráfico bipartito equilibrado modo que cada par de aristas en esté exactamente a una distancia 1 entre sí en ? (La distancia entre los bordes y es la longitud de un camino más corto desde un vértice de hasta un vértice de ).G M G e e e e MGMG
eeee

Debido a esto, la condición adicional se reduce a encontrar un subconjunto de vértices del gráfico de líneas de que están en pares exactamente a una distancia 2. Por lo tanto, el problema de encontrar un conjunto de vértices de tamaño máximo a una distancia exactamente 2 de cada otro es un problema candidato (para estar cerca del problema en cuestión). En el artículo reciente sobre los aspectos algorítmicos de la subcoloración fuerte (por MA Shalu, S. Vijayakumar, S. Devi Yamini y TP Sandhya), llaman a este problema un conjunto sólido.GL(G)G

Se sabe que el problema del conjunto de Stong es NP-completo en algunas clases de gráficos. No sé su estado en gráficos de líneas de gráficos bipartitos. El documento dice que es NP-complete en gráficos bipartitos. Nuestro interés aquí estará en la clase de gráficos lineales de gráficos bipartitos.

Antonio cirio
fuente
editado para corregir un error; Pensé que los gráficos de líneas de gráficos bipartitos son bipartitos. :)
Cyriac Antony
Creo que debería haber un +1 en su definición de distancia entre bordes (según la definición actual, los bordes de M estarían a la distancia 1 ya que hay un borde --- un camino de longitud 1 --- que conecta cada par de bordes de M, pero en realidad quieres decir distancia 2).
Florent Foucaud
lo corrigió como "los bordes ... están a una distancia uno del otro". Gracias @Florent Foucaud
Cyriac Antony
Eso funciona, pero ahora lamentablemente su "distancia de bordes" no corresponde a la distancia de vértice de los vértices correspondientes en el gráfico lineal.
Florent Foucaud
1
Para acercar el modelado a su problema, recuerde que una coincidencia máxima en un gráfico corresponde a un conjunto independiente máximo en su gráfico lineal. Por lo tanto, en el gráfico de líneas está buscando un conjunto fuerte que también sea un conjunto independiente máximo (en particular, también debe ser un conjunto dominante).
Florent Foucaud