3-мерное сопоставление
В математической дисциплине теории графов 3 -мерное паросочетание — это обобщение двудольного паросочетания (также известного как 2-мерное паросочетание) на 3-частные гиперграфы , состоящие из гиперребер, каждое из которых содержит по 3 вершины (вместо ребер, содержащих 2 вершины обычного графа).
Трехмерное сопоставление, часто сокращенно называемое 3DM , также является названием известной вычислительной задачи: нахождение наибольшего трехмерного сопоставления в заданном гиперграфе. которых оказалась доказана 3DM — одна из первых задач, NP-сложность .
Определение
[ редактировать ]Пусть X , Y и Z конечные множества, и пусть T — подмножество X × Y × Z. — То есть T состоит из троек ( x , y , z ) таких, что x ∈ X , y ∈ Y и z ∈ Z . Теперь M ⊆ T является трехмерным паросочетанием, если выполняется следующее: для любых двух различных троек ( x 1 , y 1 , z 1 ) ∈ M и ( x 2 , y 2 , z 2 ) ∈ M имеем x 1 ≠ Икс 2 , y 1 ≠ y 2 , и z 1 ≠ z 2 .
Пример
[ редактировать ]Рисунок справа иллюстрирует трехмерные сопоставления. Множество X отмечено красными точками, Y — синими точками, а Z — зелеными точками. На рисунке (а) показано множество T (серые области). На рисунке (b) показано трехмерное паросочетание M с | М | = 2, а на рисунке (c) показано трехмерное паросочетание M с | М | = 3.
Паросочетание M, показанное на рисунке (c), является максимальным трехмерным паросочетанием , т. е. оно максимизирует | М |. Сочетания, показанные на рисунках (b)–(c), являются максимальными трехмерными сопоставлениями , т. е. их нельзя расширить путем добавления дополнительных элементов из T .
Вот пример интерактивной визуализации в JavaScript.
Сравнение с двусторонним сопоставлением
[ редактировать ]Двумерное паросочетание можно определить совершенно аналогичным образом. Пусть X и Y — конечные множества, и пусть T — подмножество X × Y . Теперь M ⊆ T является двумерным паросочетанием, если выполняется следующее: для любых двух различных пар ( x 1 , y 1 ) ∈ M и ( x 2 , y 2 ) ∈ M имеем x 1 ≠ x 2 и y 1 ≠ у 2 .
В случае двумерного сопоставления набор T можно интерпретировать как набор ребер в двудольном графе G = ( X , Y , T ); каждое ребро в T соединяет вершину в X с вершиной в Y . Тогда двумерное паросочетание — это паросочетание в графе G , то есть набор попарно несмежных ребер.
Следовательно, трехмерные паросочетания можно интерпретировать как обобщение паросочетаний на гиперграфы: множества X , Y и Z содержат вершины, каждый элемент T является гиперребром, а множество M состоит из попарно несмежных ребер (ребер, которые не имеют общей вершины). В случае двумерного сопоставления Y = Z.
Сравнение с упаковкой комплекта
[ редактировать ]Трехмерное паросочетание — это частный случай упаковки множеств : мы можем интерпретировать каждый элемент ( x , y , z ) из T как подмножество { x , y , z } из X ∪ Y ∪ Z ; тогда трехмерное паросочетание M состоит из попарно непересекающихся подмножеств.
Проблема решения
[ редактировать ]В теории сложности вычислений трехмерное сопоставление (3DM) — это название следующей проблемы принятия решения : учитывая набор T и целое число k , решите, существует ли трехмерное сопоставление M ⊆ T с | М | ≥ к .
Эта проблема решения, как известно, является NP-полной ; это одна из 21 NP-полной задачи Карпа . [1] Оно NP-полно даже в том частном случае, когда k = | Х | = | Ю | = | Я | и когда каждый элемент содержится не более чем в 3 множествах, т. е. когда мы хотим идеального паросочетания в 3-регулярном гиперграфе. [1] [2] [3] В этом случае трехмерное паросочетание — это не только упаковка множества, но и точное покрытие : множество M покрывает каждый элемент X , Y и Z ровно один раз. [4] Доказательство проводится путем сокращения из 3SAT . Учитывая экземпляр 3SAT, мы создаем экземпляр 3DM следующим образом: [2] [5]
- Для каждой переменной x i существует «переменный гаджет», имеющий форму колеса. Он состоит из перекрывающихся тройников. Количество троек в два раза превышает количество вхождений в xi формулу. Есть ровно два способа охватить все вершины гаджета: один — выбрать все тройки с четными индексами, другой — выбрать все тройки с нечетными индексами. Эти два способа соответствуют установке x i в значение «истина» или «ложь». «Истинный» выбор оставляет открытой ровно одну вершину в каждом триплете с нечетным индексом, а «ложный» выбор оставляет непокрытой ровно одну вершину в каждом триплете с четным индексом.
- Для каждого предложения x i u x j u x k существует «гаджет предложения» в форме розы. Он состоит из трех перекрывающихся троек, по одному для каждой переменной в предложении. Его можно покрыть тогда и только тогда, когда хотя бы один из узлов остается непокрытым выбором переменных гаджетов.
- Поскольку возможно, что два или более узла останутся непокрытыми, нам также понадобится «гаджет для сбора мусора». По форме он напоминает большую розу. Он состоит из нескольких перекрывающихся троек, по одному на каждую вершину, которую можно оставить непокрытой в переменном гаджете. Количество таких гаджетов определяется так, чтобы их можно было обследовать ровно тогда и только тогда, когда есть удовлетворяющее задание.
Особые случаи
[ редактировать ]Существуют алгоритмы с полиномиальным временем решения 3DM в плотных гиперграфах. [6] [7]
Проблема оптимизации
[ редактировать ]Максимальное трехмерное паросочетание — это наибольшее трехмерное паросочетание. В теории сложности вычислений это также название следующей задачи оптимизации : для данного набора T найти трехмерное паросочетание M ⊆ T , которое максимизирует |M| .
Поскольку описанная выше проблема принятия решения является NP-полной, эта задача оптимизации является NP-сложной , и, следовательно, кажется, что не существует алгоритма с полиномиальным временем для поиска максимального трехмерного паросочетания. Однако существуют эффективные алгоритмы с полиномиальным временем для поиска максимального двудольного паросочетания (максимального двумерного паросочетания), например алгоритм Хопкрофта–Карпа .
Алгоритмы аппроксимации
[ редактировать ]Существует очень простой алгоритм трехмерного приближения с полиномиальным временем для трехмерного сопоставления: найдите любое максимальное трехмерное сопоставление. [8] Точно так же, как максимальное паросочетание находится в пределах 2 от максимального паросочетания, [9] максимальное трехмерное паросочетание находится в пределах 3 от максимального трехмерного паросочетания.
Для любой константы ε > 0 существует алгоритм аппроксимации с полиномиальным временем (4/3 + ε) для трехмерного сопоставления. [10]
Однако добиться лучших коэффициентов аппроксимации, вероятно, сложно: проблема APX-полна , то есть ее трудно аппроксимировать в пределах некоторой константы. [11] [12] [8]
NP-трудно достичь коэффициента аппроксимации 95/94 для максимального 3-мерного соответствия и коэффициента аппроксимации 48/47 для максимального 4-мерного соответствия. Твердость сохраняется даже тогда, когда она ограничена экземплярами, в которых каждый элемент встречается ровно два раза. [13]
Параллельные алгоритмы
[ редактировать ]вычислений существуют различные алгоритмы трехмерного сопоставления В модели массово-параллельных . [14]
См. также
[ редактировать ]- Список NP-полных задач
- Независимый от радуги набор - проблема, которую можно решить с помощью трехмерного сопоставления.
- Числовое трехмерное сопоставление
Примечания
[ редактировать ]- ^ Перейти обратно: а б Карп (1972) .
- ^ Перейти обратно: а б Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . , раздел 3.1 и задача SP1 в Приложении А.3.1.
- ^ Корте, Бернхард ; Виген, Йенс (2006), Комбинаторная оптимизация: теория и алгоритмы (3-е изд.), Springer , раздел 15.5.
- ^ Пападимитриу и Стейглиц (1998) , раздел 15.7.
- ^ Демейн, Эрик (2016). «16. Сложность: P, NP, NP-полнота, Сокращение» . Ютуб .
- ^ Карпинский, Ручинский и Шиманска (2009)
- ^ Киваш, Нокс и Майкрофт (2013)
- ^ Перейти обратно: а б Мэй (1991)
- ^ Сопоставление (теория графов)#Свойства .
- ^ Циган, Марек (2013). «Улучшенное приближение для трехмерного сопоставления с помощью локального поиска с ограниченной шириной пути». 54-й ежегодный симпозиум IEEE по основам информатики , 2013 г. стр. 509–518. arXiv : 1304.1424 . Бибкод : 2013arXiv1304.1424C . дои : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7 . S2CID 14160646 .
- ^ Крещенци и др. (2000) .
- ^ Аузиелло и др. (2003) , задача SP1 в Приложении Б.
- ^ Хлебик, Мирослав; Хлебикова, Янка (4 апреля 2006 г.). «Сложность аппроксимации ограниченных вариантов задач оптимизации» . Теоретическая информатика . Основы теории вычислений (FCT 2003). 354 (3): 320–338. дои : 10.1016/j.tcs.2005.11.029 . ISSN 0304-3975 .
- ^ Хангир, Усама; Штейн, Клиффорд (21 сентября 2020 г.). «Распределенные алгоритмы сопоставления в гиперграфах». arXiv : 2009.09605 [ cs.DS ].
Ссылки
[ редактировать ]- Аузиелло, Джорджо; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer .
- Крещенци, Пьерлуиджи; Канн, Вигго; Халльдорссон, Магнус; Карпински, Марек ; Вегингер, Герхард (2000), «Максимальное трехмерное сопоставление», Сборник задач оптимизации NP .
- Канн, Вигго (1991), «Максимально ограниченное трехмерное сопоставление является MAX SNP-полным», Information Processing Letters , 37 (1): 27–35, doi : 10.1016/0020-0190(91)90246-E .
- Карп, Ричард М. (1972), «Сводимость комбинаторных задач», Миллер, Раймонд Э.; Тэтчер, Джеймс В. (ред.), Сложность компьютерных вычислений , Пленум, стр. 85–103 .
- Карпински, Марек ; Ручинский, Анджей; Шиманска, Эдита (2009), «Сложность задач идеального сопоставления на плотных гиперграфах», ISAAC '09, Труды 20-го Международного симпозиума по алгоритмам , Конспекты лекций по информатике, 5878 : 626–636, doi : 10.1007/978-3 -642-10631-6_64 , ISBN 978-3-642-10630-9 .
- Киваш, Питер; Нокс, Фиахра; Майкрофт, Ричард (2013), «Идеальные паросочетания за полиномиальное время в плотных гиперграфах», Труды сорок пятого ежегодного симпозиума ACM по теории вычислений , стр. 311–320, arXiv : 1307.2608 , Bibcode : 2013arXiv1307.2608K , doi : 10.1145/2488608.2488647 , ISBN 9781450320290 , S2CID 5393523
{{citation}}: CS1 maint: дата и год ( ссылка ) . - Пападимитриу, Христос Х .; Стейглиц, Кеннет (1998), Комбинаторная оптимизация: алгоритмы и сложность , Dover Publications .