Encontrar una cobertura mínima de un subconjunto de un producto cartesiano finito por productos cartesianos

11

Dado un subconjunto de un producto cartesiano de dos conjuntos finitos, deseo encontrar una cobertura mínima de él por conjuntos que son productos cartesianos.I×J

Por ejemplo, dado un producto entre y , puedo observar el subconjunto e intente cubrirlo con un número mínimo de productos cartesianos.I={A,B,C}J={1,2,3}{(A,2),(B,3),(B,2)}

Dos formas de hacerlo son y , ambos requieren 2 productos. Una solución subóptima puede dividirla en 3 productos triviales.{A}×{2}+B×{2,3}{A,B}×{2}+{B}×{3}

¿Se puede encontrar una cobertura tan óptima de manera eficiente (por ejemplo, en tiempo polinómico)?

algorithms set-cover yuvalm2
fuente
me recuerda este problema, "factorizar la unión cartesiana de vectores de bits" (cstheory.SE, redactado de manera muy diferente) que tiene conexiones con los límites inferiores de la teoría de circuitos. ¿en qué contexto surge tu problema?
vzn
Mi contexto es la seguridad de la red. En una red grande con muchos servidores, una política de seguridad define cuál puede hablar con cuál. Si dicha política se construye de forma incremental durante un largo período de tiempo (como suele ser), la descripción de la política de seguridad puede simplificarse fusionando las reglas de seguridad. Deseo encontrar una óptima tal simplificación.
yuvalm2
¿Es solo la cantidad de productos que desea minimizar? Si es así, ¿qué tiene de malo usar como tu portada? Eso cubrirá todo en su subconjunto (y algo más). ¿Tiene el requisito de que la solución no solo cubra el subconjunto, sino que también evite cubrir cualquier cosa fuera del subconjunto? I×J
DW
1
Además, dado que esto proviene de una aplicación práctica (y probablemente esté buscando soluciones prácticas), ¿puede darnos una idea de los tamaños típicos de los parámetros? por ejemplo, el tamaño típico de,y su subconjunto, dentro de un orden de magnitud más o menos; o rangos de valores típicos? Esto podría ayudar a evaluar qué técnicas tienen más probabilidades de ser efectivas. Recuerdo los mapas de minimización lógica , DNF y Karnaugh . |I||J|
DW
3
Tal vez otra manera de formular este es el siguiente: Dado un bipartito gráfico encontrar un número mínimo de camarillas bipartitas (o bi-camarillas) que cubren . Cada camarilla corresponde a un producto único en su espacio cartesiano. G=(L,R,E)E
Nicholas Mancuso

Respuestas:

2

NM reformula este problema en comentarios al encontrar un número mínimo de camarillas bipartitas (bi-camarillas) que cubren un gráfico bipartito. Los dos conjuntos que menciona son los 2 conjuntos de vértices del gráfico bipartito. Los productos cartesianos de los subconjuntos de los dos conjuntos de vértices son bicliques. Wikipedia dice que este es el problema de la dimensión bipartita y es el problema GT18 en Garey y Johnson , se demostró que NP está completo basado en una reformulación directa del problema SP7 de base establecida.

vzn
fuente