Нахождение минимального покрытия подмножества конечного декартова произведения декартовыми произведениями

11

Учитывая подмножество декартового произведения из двух конечных множеств, я хочу найти его минимальное покрытие множествами, которые сами являются декартовыми произведениями.я×J

Например, учитывая произведение между и , я могу наблюдать подмножество и постарайтесь покрыть это минимальным количеством декартовых произведений.J = { 1 , 2 , 3 } { ( A , 2 ) , ( B , 3 ) , ( B , 2 ) }язнак равно{A,В,С}Jзнак равно{1,2,3}{(A,2),(В,3),(В,2)}

Это можно сделать двумя способами: и , оба требуют 2 продукта. Неоптимальным решением может быть разбиение его на 3 тривиальных продукта.{A}×{2}+В×{2,3}{A,В}×{2}+{В}×{3}

Можно ли найти такое оптимальное покрытие эффективно (например, за полиномиальное время)?

algorithms set-cover yuvalm2
источник
напоминает мне об этой проблеме, «факторизации декартового объединения битовых векторов» (cstheory.SE, формулируется очень по-разному), которая связана с нижними границами теории цепей. в каком контексте возникает ваша проблема?
vzn
Мой контекст - безопасность сети. В большой сети с большим количеством серверов политика безопасности определяет, с кем можно говорить. Если такая политика создается постепенно в течение длительного периода времени (как это обычно бывает), описание политики безопасности может быть упрощено путем объединения правил безопасности вместе. Я хочу найти оптимальное такое упрощение.
yuvalm2
Это только количество продуктов, которые вы хотите минимизировать? Если так, что не так с использованием качестве обложки? Это будет охватывать все в вашем подмножестве (и некоторые другие). Есть ли у вас требование, что решение должно не только охватывать подмножество, но также и избегать охвата чего-либо за пределами подмножества? я×J
DW
1
Кроме того, поскольку это происходит из практического применения (и поэтому вы, вероятно, ищете практические решения), можете ли вы дать представление о типичных размерах параметров? например, типичный размер,и ваше подмножество, с точностью до порядка или около того; или диапазоны типичных значений? Это может помочь оценить, какие методы наиболее эффективны. Мне напоминают о минимизации логики , DNF и картах Карно . | J ||я||J|
DW
3
Возможно , еще один способ сформулировать это состоит в следующем: Учитывая двудольный граф , найти минимальное число двудольных клик (или би-клик) , которые покрывают . Каждая клика соответствует уникальному произведению в вашем декартовом пространстве. Eграммзнак равно(L,р,Е)Е
Николас Манкузо

Ответы:

2

ЯМ формулирует эту проблему в комментариях как нахождение минимального числа двудольных клик (bi-cliques), которые покрывают двудольный граф. два набора, которые вы упомянули, являются двумя наборами вершин двудольного графа. декартовы произведения подмножеств двух вершин являются бикликами. Википедия утверждает, что это проблема двухстороннего измерения и проблема GT18 у Гарея и Джонсона , доказавшая, что NP завершена, на основе простой переформулировки задачи базиса множеств SP7.

ВЗН
источник