Trouver une couverture minimale d'un sous-ensemble d'un produit cartésien fini par des produits cartésiens

Étant donné un sous-ensemble d'un produit cartésien de deux ensembles finis, je souhaite en trouver une couverture minimale par des ensembles qui sont eux-mêmes des produits cartésiens. $I \times J$

Par exemple, étant donné un produit entre et , je peux observer le sous-ensemble et essayez de le couvrir avec un nombre minimal de produits cartésiens. $I=\{A,B,C\}$ $J=\{1,2,3\}$ $\{(A,2), (B,3), (B,2)\}$

Il existe deux façons de procéder: et , les deux nécessitant 2 produits. Une solution sous-optimale peut la diviser en 3 produits triviaux. $\{A\} \times \{2\} + B \times \{2,3\}$ $\{A,B\}\times \{2\} + \{B\}\times \{3\}$

Une telle couverture optimale peut-elle être trouvée efficacement (par exemple, en temps polynomial)?

algorithms set-cover yuvalm2
la source

me rappelle ce problème, "la factorisation de la jointure cartésienne des vecteurs de bits" (cstheory.SE, formulée de manière très différente) qui a des connexions avec les limites inférieures de la théorie des circuits. dans quel contexte se pose votre problème?

vzn

Mon contexte est la sécurité du réseau. Dans un grand réseau avec de nombreux serveurs, une politique de sécurité définit qui peut parler avec qui. Si une telle stratégie est construite de manière incrémentielle sur une longue période de temps (comme c'est généralement le cas), la description de la stratégie de sécurité peut être simplifiée en fusionnant les règles de sécurité. Je souhaite trouver une telle simplification optimale.

yuvalm2

I \times J

$I \times J$

| I |

$|I|$

| J |

$|J|$

G = (L, R, E)

$G = (L, R, E)$

E

$E$

Réponses:

NM reformule ce problème dans les commentaires en trouvant le nombre minimum de cliques bipartites (bi-cliques) qui couvrent un graphe bipartite. les deux ensembles que vous mentionnez sont les 2 ensembles de sommets du graphe bipartite. les produits cartésiens des sous-ensembles des deux ensembles de sommets sont bicliques. wikipedia indique qu'il s'agit du problème de dimension bipartite et du problème GT18 à Garey et Johnson , NP complet prouvé sur la base d'une reformulation simple du problème de base d'ensemble SP7.

vzn
la source