¿Es la intersección de

16

Se sabe que la intersección de tres matroides generales es NP-hard ( fuente ), que se realiza a través de la reducción del ciclo hamiltoniano. La reducción utiliza un matroide gráfico y dos matroides de conectividad.

Un caso especial de un problema en el que estoy trabajando puede resolverse mediante la intersección de múltiples matroides gráficos, pero no he podido encontrar si este problema está en P.

Pregunta: ¿Se sabe? ¿Alguien puede referirme a un papel o algo así?

( Nota: he hecho esta pregunta en Ciencias de la Computación y me remitieron aquí).

reference-request np-hardness reductions Matej Konecny
fuente

Respuestas:

11

Creo que todavía está NP-completo, por una reducción de los caminos hamiltonianos en gráficos bipartitos con vértices de dos grados uno y todos los demás vértices que tienen grado tres. (Esto es lo mismo que encontrar ciclos hamiltonianos a través de un borde especificado en un gráfico bipartito cúbico; reemplace el borde especificado por dos hojas).

K3K2

David Eppstein
fuente
8

¿Qué tal si utilizamos el hecho de que la correspondencia 3-d es NP completa para mostrar la integridad de NP de este problema? Podemos escribir fácilmente coincidencias tridimensionales como intersección de 3 matroides de partición, y un matroide de partición es un caso especial de un matroide gráfico (considere un gráfico con bordes paralelos).

Sahil Singla
fuente
3
No es cierto que un matroide de partición sea siempre un matroide gráfico, pero en su caso desea elegir exactamente un elemento de cada parte, y ese matroide es gráfico.
Sasho Nikolov