Finden einer minimalen Abdeckung einer Teilmenge eines endlichen kartesischen Produkts durch kartesische Produkte

11

Angesichts einer Teilmenge eines kartesischen Produkts aus zwei endlichen Mengen möchte ich eine minimale Abdeckung davon durch Mengen finden, die selbst kartesische Produkte sind.I×J

Wenn beispielsweise ein Produkt zwischen und J = { 1 , 2 , 3 } gegeben ist , kann ich die Teilmenge { ( A , 2 ) , ( B , 3 ) , ( B , 2 ) beobachten. } und versuchen, es mit einer minimalen Anzahl kartesischer Produkte abzudecken.I={A,B,C}J={1,2,3}{(A,2),(B,3),(B,2)}

Zwei Möglichkeiten hierfür sind und { A , B } × { 2 } + { B } × { 3 } , für die beide zwei Produkte erforderlich sind. Eine suboptimale Lösung kann darin bestehen, sie in drei triviale Produkte aufzuteilen.{A}×{2}+B×{2,3}{A,B}×{2}+{B}×{3}

Kann eine solche optimale Abdeckung effizient gefunden werden (z. B. in Polynomzeit)?

algorithms set-cover yuvalm2
quelle
erinnert mich an dieses Problem, "die kartesische Verknüpfung von Bitvektoren zu berücksichtigen " (cstheory.SE, sehr unterschiedlich formuliert), das Verbindungen zur unteren Grenze der Schaltungstheorie hat. In welchem ​​Kontext tritt Ihr Problem auf?
VZN
Mein Kontext ist Netzwerksicherheit. In einem großen Netzwerk mit vielen Servern definiert eine Sicherheitsrichtlinie, welche mit welchen sprechen dürfen. Wenn eine solche Richtlinie über einen langen Zeitraum inkrementell erstellt wird (wie es normalerweise der Fall ist), kann die Beschreibung der Sicherheitsrichtlinie durch Zusammenführen von Sicherheitsregeln vereinfacht werden. Ich möchte eine optimale solche Vereinfachung finden.
Yuvalm2
I×J
1
|I||J|
3
Vielleicht ist eine andere Möglichkeit, dies zu formulieren, die folgende: Gegeben ein zweigeteilter Graph G=(L.,R.,E.) Finden Sie eine Mindestanzahl von zweigliedrigen Cliquen (oder Bi-Cliquen), die diese abdecken E.. Jede Clique entspricht einem einzigartigen Produkt in Ihrem kartesischen Raum.
Nicholas Mancuso

Antworten:

2

NM formuliert dieses Problem in Kommentaren neu, indem es eine Mindestanzahl von zweigliedrigen Cliquen (Bi-Cliquen) findet, die einen zweigliedrigen Graphen abdecken. Die beiden von Ihnen erwähnten Sätze sind die beiden Scheitelpunktsätze des zweigeteilten Graphen. Die kartesischen Produkte von Teilmengen der beiden Scheitelpunktmengen sind Bicliques. Wikipedia gibt an, dass dies das zweigliedrige Dimensionsproblem ist und das Problem GT18 in Garey und Johnson ist , das sich aufgrund der einfachen Neuformulierung des Satzbasisproblems SP7 als NP-vollständig erwiesen hat.

vzn
quelle