Рассмотрим набор множеств над базовым множеством где и , и пусть будет положительным целым числом.F = { F 1 , F 2 , … , F n } U = { e 1 , e 2 , … , e n } | F i | « П е я ∈ F я к
Цель состоит в том, чтобы найти другой набор множеств над , чтобы каждый мог быть записан как объединение не более чем взаимно непересекающихся множеств. в а также мы хотимбыть минимальным (т. е. совокупное количество элементов во всех наборах должно быть как можно меньше).С = { С 1 , С 2 , ... , С т } U Р я K ( K < < | C | )
Обратите внимание, что имеет такой же размер с , но размер является неопределенным.F U C
Кто-нибудь может сказать, является ли вышеуказанная проблема NP-трудной? (установить покрытие? упаковка? идеальное покрытие)
Спасибо за ваше время.
Ответы:
Лемма. Проблема NP-сложная.
Эскиз доказательства. Мы игнорируем ограничения | F i | ≪ n = | U | в опубликованной задаче, поскольку для любого экземпляра задачи ( F , U , k ) экземпляр ( F ′ = F n , U ′ = U n , k ) получается путем объединения n независимых копий ( F , U , K ) (где я|Fi|≪n=|U| (F,U,k) (F′=Fn,U′=Un,k) n ( F, U, к ) я й экземпляр F использует я й копии U в качестве базового набора) эквивалентен, и удовлетворяет ограничение (оно имеет | F ' я | & le ; п « п 2 = | U ' | ).F я U | F'я| ≤n≪ n2= | U'|
Мы даем скидку от 3-сат. Для наглядности на первом этапе редукции мы игнорируем ограничения e i ∈ F i в опубликованной задаче. На втором этапе мы опишем, как удовлетворить эти ограничения при сохранении правильности сокращения.ея∈ Fя
Начальная ступень. Зафиксируйте любую формулу 3-SAT ϕ . Предположим, что в WLOG каждое предложение содержит ровно три литерала (каждый использует свою переменную). Создайте следующий экземпляр ( F , U , k ) опубликованной проблемы с k = 3 .φ ( F, U, к ) к = 3
Пусть n будет числом переменных в ϕ . Есть 3 п + 1 элементов в U : один элемент т (для «истина»), и для каждой переменной х I в ф , три элемента х I , ¯ х я и е I (для «ложь»).N φ 3 н + 1 U T Икся φ Икся Икс¯¯¯я ея
Для каждого элемента в U существует множество синглтона , содержащее только этот элемент в F . Любое решение С , следовательно , включает в себя каждый из этих наборов, которые способствуют их общий размер 3 п + 1 к стоимости C .U F С 3 н + 1 С
Кроме того, для каждой переменной х I в ф существует множество «переменная» { х я , ¯ х я , F I , т } в F . Для каждого предложения в ϕ существует множество «предложений» в F, состоящее из литералов в предложении и t . Так , например, положение х 1 ∧ ¯ х 2 ∧ х 3 дает множество { х 1 , ¯ х 2 , хИкся φ { хя, х¯¯¯я, фя, т } F φ F T Икс1∧ х¯¯¯2∧ х3 3 , т } в F .{х1, х¯¯¯2,х3, т } F
Утверждение 1. Сокращение корректно: ϕ выполнимо тогда и только тогда, когда какое-либо решение C имеет стоимость ∑ j | C j | = 5 н + 1 .φ С ΣJ|СJ| =5н+1
(только если) Пусть ϕ выполнимо. Построим решение C, состоящее из 3 n + 1 одноэлементных множеств, плюс для каждой переменной x i пара, состоящая из истинного литерала и t . (Например, { ¯ х я , т } , если х я ложно.) Стоимость C затем 5 п + 1 .φ С 3 н + 1 Икся T { х¯¯¯я, т } Икся С 5 н + 1
Каждый набор переменной { х я , ¯ х я , F I , т } является объединением трех множеств: пара , состоящей из истинных буквальных и т , плюс два набора одноэлементных, по одному для каждого из двух других элементов. (Например, { ¯ х я , т } , { х я } , { е I } .){хя, х¯¯¯я,фя, т } T { х¯¯¯я, т } , {хя} , { fя}
Каждый набор раздела (например , { х 1 , ¯ х 2 , х 3 , т } ) является объединением трех множеств: пара , состоящая из т и истинного буквальным, плюс два набора одноэлементных, по одному для каждого из двух других литералов. (Например, { х 1 , т } , { ¯ х 2 } , { х 3 } .){х1, х¯¯¯2,х3, т } T {х1, т } , { х¯¯¯2} , { x3}
(если) Предположим, что существует решение C размером 5 n + 1 . Решение должно содержать 3 n + 1 одноэлементных набора, а также другие наборы с общим размером 2 n .С 5 н + 1 3 н + 1 2 н
Рассмотрим сначала п «переменной» наборов, каждый из вида { х я , ¯ х я , F I , т } . Множество является объединением непересекающихся не более трех множеств C . Без ограничения общности это несвязное объединение двух синглетонов и пары (в противном случае разбиение множеств в C достигает этого без увеличения стоимости). Обозначим пару P i . Пары P i и P j для разных переменных x i и x j различны, посколькуN {хя, х¯¯¯я,фя, т } С С пя пя пJ Икся ИксJ Р я содержу й я , ¯ х я , или е я , но Р J нет. Следовательно, сумма размеров этих пар равна 2 n . Таким образом, эти пары являются единственными не-одиночными множествами в решении. пя Икся Икс¯¯¯я ея пJ 2 н
Далее рассмотрим «положения» устанавливает, например, { х я , ¯ х J , х к , т } . Каждый такой набор должен быть объединением не более трех наборов в C , то есть до двух одноэлементных наборов и по меньшей мере одной пары P i , P j или P k . При обследовании пар и множества п, оно должно быть объединение двух одноэлементных и одной пары, и эта пара должна иметь вид { х я , т } или { ¯ х J , т }{хя, х¯¯¯J,хК, т } С пя пJ пК {хя, т } { х¯¯¯J, т } (буквальное и т ).T
Следовательно, следующее назначение удовлетворяет ф : правопреемником истинные каждой переменной х я такое , что Р я = { х я , т } , правопреемником ложь каждой переменной х я такое , что Р я = { ¯ х я , т } , и назначить остальные переменные произвольно.φ Икся пя= {хя, т } Икся пя= { х¯¯¯я, т }
Этап 2. Произведенный выше экземпляр ( F , U , k = 3 ) не удовлетворяет ограничению e i ∈ F i, указанному в описании задачи. Исправьте этот недостаток следующим образом. Упорядочите множества F i и элементы e i в U так, чтобы каждый одноэлементный набор соответствовал своему элементу e i . Пусть m - количество предложений в ϕ , поэтому | F | = 1 + 4 n +(F,U, к = 3 ) ея∈Fя Fя ея U ея м φ м и | U | = 1 + 3 н .|F|=1+4n+m |U|=1+3n
Пусть ( F ′ , U ′ , k ′ = 4 ) обозначает случай, полученный следующим образом. Пусть быть множество 2 п + 2 м новых элементов искусственных, два для каждого не одноточечного множества в F . Пусть U ' = U ∪ A . Пусть F ' содержит наборы одноэлементные из F , плюс, для каждого не одноточечного множества F я в F , два множества F я ∪ { в(F′,U′,k′=4) A 2n+2m F U′=U∪A F′ F Fi F i , a ' i } и { a i , a ' i } , где a i и a ' i являются двумя элементами в A, выбранными уникально для F i . Сейчас | F ′ | = | U ′ | = 1 + 5 n + 2 m и (при правильном упорядочении F ′ и U ′ ) ограничение eFi∪{ai,a′i} {ai,a′i} aя a'я A Fя | F'| = | U'| =1+5н+2м F' U' ′ I ∈F ′ i выполняется для каждого множестваF ′ i .е'я∈ F'я F'я
В заключение отметим, что ( F ′ , U ′ , k ′ = 4 ) имеет решение стоимости | A | + 5 n + 1, если исходный экземпляр ( F , U , k = 3 ) имеет решение стоимостью 5 n + 1 .( F', U', к'= 4 ) |A|+5n+1 (F,U, к = 3 ) 5 н + 1
(если) Учитывая любое решение C стоимостью 5 n + 1 для ( F , U , k = 3 ) , добавление n + m устанавливает { a i , a ′ i } (по одному для каждого не-одиночного F i , поэтому разбиение A ) на C дает решение ( F ′ , U ′ , k ′ = 4 ) стоимостиС 5n+1 (F,U,k=3) n+m {ai,a′i} | A | + c o s t ( C ) = | A | + 5 н + 1 .
(только если) Рассмотрим любое решение C ′ для ( F ′ , U ′ , k = 4 ) стоимости | A | + 5 н + 1 . Рассмотрим любую пару без одноэлементные множества F я ∪ { я , в " я } и { в I , ' я } в F ' . Каждый является несвязанным объединением не более 4 множеств в C′ . По аргументу local-exchange один из этих наборов является { a i , a ′ i }, а остальные не содержат a i или a ′ i - в противном случае это свойство может быть достигнуто путем локальной модификации наборов, без увеличения стоимости ... (недостаток деталей, вот почему я называю этоэскизом). Таким образом, удаление { a i , a ′ i } множеств из C ′ дает решение C для ( F , U ,k = 3 ) стоимостью 5 н + 1 . ⋄
источник