Сложность нахождения максимального числа попарно непересекающихся множеств

9

Предположим, что у меня есть P наборы с элементами, взятыми из rвозможные. Каждый набор имеет размерn (n<r), где наборы могут перекрываться. Я хочу определить, являются ли следующие две проблемы NP-полными или нет:

Проблема А. Есть лиM (1MP) различные наборы внутриP множества (т.е. их попарное пересечение пусто)?

Проблема Б. Теперьk (k<n) элементы могут быть выбраны из каждого набора. ЗдесьL (1LP) различные наборы размераk каждый в пределах Pнаборы? Обратите внимание, что только один наборk элементы могут быть взяты из каждого набора n элементы.

Замечание : меня в основном интересует случай, когдаk,n исправлены (n2,k2).

Я думаю, что проблема А может рассматриваться как n-равномерная rпроблема согласования гиперграфа. То есть у нас есть элементыr как вершины, и каждый гипер-край содержит подмножество n вершины графа.

  1. в n-равномерная rпроблема согласования гиперграфа NP-полная?

  2. Я думаю, что проблема B эквивалентна нахождению числа различных гипер-ребер мощности k взяты из гипер-краев мощности n, Это ограниченная версия (в том смысле, что каждыйk-кардинальный набор берется из предварительно выбранного набора n элементы, а не взяты произвольно из r элементы) задачи NP-полной?

Пример (n=3,r=5,P=3):

A={1,2,3}, B={2,3,4}, C={3,4,5}

Если k=n=3, есть только M=1 один отдельный набор, который A или B или C, так как каждая из пар (A,B), (A,C), (B,C) имеет непустое пересечение.

Если k=2, у нас есть L=2 различные наборы: одно решение {1,2}, {3,4} (подмножества A а также B).

МЖК
источник

Ответы:

2

Это особый случай проблемы упаковки с максимальным набором, и обе проблемы A и B являются NP-Complete . Обратите внимание, что проблема является просто проблемой соответствия, еслиn=2 и это также легко, если n=1, Так что я придуn3,

Вместо того, чтобы задавать вопрос,

Здесь M непересекающиеся множества среди P наборы?

Давайте зададим следующий вопрос

Какое максимальное количество непересекающихся множеств мы можем получить из P наборы?

Ясно, что если второй вопрос отвечает за полиномиальное время, то и первый так же, так как все, что нам нужно сделать, это сравнить это максимальное значение с Mи выведите YES, еслиMменьше или равно этому максимуму и НЕТ в противном случае.

Кроме того, если первый вопрос отвечает за полиномиальное время, то второй тоже слишком, поскольку мы можем использовать бинарный поиск на M и получить ответ на второй вопрос и добавить только фактор O(logM)

Таким образом, мы можем сделать вывод, что оба вопроса эквивалентны. т. е. вопрос 1 разрешается в полиномиальное время тогда и только тогда, когда вопрос 2 тоже.

Также ясно, что проблемы в NP, так как мы можем легко проверить, что M Множества излагаемые являются непересекающимися.

Таким образом, вопрос теперь состоит в том, как мы сводим к этому известную проблему NP-Hard? Для этого мы избавляемся от задачи максимального набора упаковки . Я просто сконцентрируюсь на проблеме А, поскольку проблему В легко показать трудной, установивk=n1

Рассмотрим произвольный случай задачи упаковки максимального множества T, Обратите внимание, что единственная разница между задачей A и исходной проблемой упаковки максимальных наборов состоит в том, что в задаче A размер наборов должен быть одинаковым. Позволятьt быть максимальным количеством элементов среди всех наборов в T, Если каждый набор вT иметь одинаковую мощность, мы закончили, и проблема покрытия множества - это точно проблема A. Теперь предположим, что для некоторого множества SiT, у нас есть |Si|<t, Мы просто добавляем(t|Si|) элементы к Si которые не являются элементами любого набора в T, Мы повторяем этот процесс, пока все наборыSiTимеют одинаковый размер. Понятно, что добавление новых элементов таким способом не меняет размер максимального числа непересекающихся множеств.

Итак, если мы можем решить проблему A за полиномиальное время мы можем решить проблему упаковки максимального набора за полиномиальное время, так как все, что нам нужно сделать, это удалить дополнительные элементы, которые мы добавили, и это не изменит размер максимального числа непересекающихся множеств в T,

РЕДАКТИРОВАТЬ - Некоторые Дополнительная информация о проблеме B

Предположим, что задача B имеет решение за полиномиальное время, теперь рассмотрим произвольный случай T проблемы А с nэлементов в наборе. Теперь мы добавляем фиктивный элементd к каждому набору в T, Теперь мы задаем следующий вопрос.

Какое максимальное количество непересекающихся множеств мы можем получить, взяв n элементы из каждого набора?

Теперь мы знаем, что среди наборов в максимуме не более одного из них может содержать фиктивный элемент, поэтому, если ответ, который мы получаем как максимум, равен M, то фактическое максимальное количество наборов в экземпляре T (наша первоначальная проблема А) либо M или (M1), но это дает постоянный коэффициент приближения для максимальной упаковки набора. И такое приближение возможно только еслиP=NP, Так что проблема Б тоже сложная.

Обинна
источник
Относительно проблемы B: если вы добавляете фиктивный элемент ко всем наборам задачи A, вы получаете наборы размера n+1, В примере, который появляется в моем вопросе (n=3,P=3), вы получите максимальное количество непересекающихся наборов размеров n1=2 это 3: {1,d},{2,3},{4,5}, Однако решение проблемы A состоит в том, что существует только один набор. Другими словами, я не вижу, как решение проблемы B дает постоянное приближение фактора к проблеме A.
MJK
Если вы добавите фиктивный элемент, у вас есть наборы A={1,2,3,d},B={2,3,4,d} а также C={3,4,5,d}, Этот новый экземпляр сn=4 является примером проблемы A, которая нас интересует. Теперь запустите предполагаемый алгоритм B на этих множествах, т.е. n=4 а также k=3, Это то, что я говорю. Обратите внимание, что проблема сводится к поиску максимального соответствия, еслиn=2 или k=2,
Обинна Окечукву