Jump to content

Доминирующий набор

Три доминирующих набора одного и того же графа (красным). Число доминирования этого графа равно 2: (б) и (в) показывают, что существует доминирующее множество с 2 вершинами и не существует доминирующего множества только с 1 вершиной.

В теории графов для доминирующим множеством графа G является подмножество D его вершин, такое, что любая вершина находится в D или имеет соседа в D. G Число доминирования γ( G ) — это количество вершин в наименьшем доминирующем множестве для G .

Проблема доминирующего множества касается проверки того, является ли γ( G ) ⩽ K для данного графа G и входных данных K ; это классическая NP-полная задача решения в теории сложности вычислений . [1] Поэтому считается, что не может быть алгоритма , который мог бы вычислить γ( G ) для всех графов G. эффективного Однако существуют эффективные алгоритмы аппроксимации , а также эффективные точные алгоритмы для определенных классов графов.

Доминирующие множества представляют практический интерес в нескольких областях. В беспроводных сетях доминирующие наборы используются для поиска эффективных маршрутов в одноранговых мобильных сетях. Они также использовались при обобщении документов и при проектировании безопасных систем для электрических сетей .

Формальное определение

[ редактировать ]

Учитывая неориентированный граф G = ( V , E ) , подмножество вершин называется доминирующим множеством, если для каждой вершины , есть вершина такой, что .

Каждый граф имеет хотя бы одно доминирующее множество: если множество всех вершин, то по определению D является доминирующим множеством, так как не существует вершины . Более интересная задача — найти небольшие доминирующие множества. Число доминирования G : определяется как .

Варианты

[ редактировать ]

Связное доминирующее множество это доминирующее множество, которое также связно . Если S — связное доминирующее множество, можно сформировать остовное дерево G , в котором S образует множество нелистовых вершин дерева; и наоборот, если T — любое остовное дерево в графе с более чем двумя вершинами, нелистовые вершины T образуют связное доминирующее множество. Следовательно, поиск минимального связного доминирующего множества эквивалентен поиску остовного дерева с максимально возможным числом листьев.

Полный доминирующий набор (или сильно доминирующий набор ) — это набор вершин, такой, что все вершины в графе, включая сами вершины в доминирующем множестве, имеют соседа в доминирующем множестве. [2] То есть: для каждой вершины , есть вершина такой, что . На рисунке (c) выше показано доминирующее множество, которое представляет собой связное доминирующее множество и полное доминирующее множество; примеры на рисунках (a) и (b) не являются ни тем, ни другим. В отличие от простого доминирующего множества, полное доминирующее множество может не существовать. Например, граф с одной или несколькими вершинами и без ребер не имеет полного доминирующего множества. Число сильного доминирования G : определяется как ; очевидно, .

Доминирующее множество ребер — это множество ребер (пар вершин), объединение которых является доминирующим множеством; такого множества может не существовать (например, его не имеет граф с одной или несколькими вершинами и без ребер). Если оно существует, то объединение всех его ребер является сильно доминирующим множеством. Следовательно, наименьший размер множества с доминирующим ребром не менее .

Напротив, набор с доминированием ребер - это набор D ребер, такой, что каждое ребро, не входящее в D , смежно хотя бы с одним ребром в D ; такое множество всегда существует (например, множество всех ребер является множеством с доминирующим ребром).

k k -доминирующее множество — это такое множество вершин, что каждая вершина, не входящая в набор, имеет не менее соседей в множестве (стандартное доминирующее множество — это 1-доминирующее множество). Аналогично, k доминирующий набор из -кортежа — это такой набор вершин, что каждая вершина в графе имеет не менее k соседей в этом множестве (общий доминирующий набор — это доминирующий набор из 1 кортежа). -аппроксимация (1 + log n ) минимального доминирующего набора из k -кортежа может быть найдена за полиномиальное время. [3] Каждый граф допускает k -доминирующее множество (например, множество всех вершин); но только графы с минимальной степенью k - 1 допускают доминирующее множество из k -кортежа. Однако даже если граф допускает доминирующий набор из k -кортежей, минимальный из k доминирующий набор -кортежей может быть почти в k раз больше, чем минимальный доминантный набор из k -кортежей для того же графа; [4] -аппроксимация (1,7 + log Δ) минимального k -доминирующего набора также может быть найдена за полиномиальное время.

Множество с доминированием звезды — это подмножество D множества V такое, что для каждой вершины v в V звезда v в v (набор ребер, смежных с ) звезду некоторой вершины D. пересекает Очевидно, что если G имеет изолированные вершины , то в ней нет множеств, доминирующих по звездам (поскольку звезда изолированных вершин пуста). Если G не имеет изолированных вершин, то каждое доминирующее множество является звездно-доминирующим множеством, и наоборот. Различие между звездным доминированием и обычным доминированием становится более существенным, если рассматривать их дробные варианты. [5]

Доматическое разбиение — это разбиение вершин на непересекающиеся доминирующие множества. Доматическое число — это максимальный размер домашнего раздела.

Вечное доминирующее множество — это динамическая версия доминирования, в которой вершина v в доминирующем множестве D выбирается и заменяется соседом u ( u нет в D ), так что модифицированное D также является доминирующим множеством, и этот процесс можно повторить. над любой бесконечной последовательностью выборов вершин v .

Доминирующие и независимые множества

[ редактировать ]

Доминирующие множества тесно связаны с независимыми множествами : независимый набор также является доминирующим множеством тогда и только тогда, когда он является максимальным независимым набором , поэтому любой максимальный независимый набор в графе обязательно является также минимальным доминирующим набором.

Доминирование независимых наборов

[ редактировать ]

Доминирующая совокупность может быть независимой, а может и не быть независимой. Например, на рисунках (a) и (b) выше показаны независимые доминирующие множества, а на рисунке (c) показан доминирующий набор, который не является независимым набором.

Независимое число доминирования i ( G ) графа G — это размер наименьшего доминирующего набора, который является независимым набором. Эквивалентно, это размер наименьшего максимального независимого множества. Минимум в i ( G ) берется за меньшее количество элементов (рассматриваются только независимые множества), поэтому γ ( G ) ≤ i ( G ) для всех G. графов

Неравенство может быть строгим — существуют графы G , для которых γ ( G ) < i ( G ) . Например, пусть G двойной звездчатый граф , состоящий из вершин , где п , q > 1 . Ребра G определяются следующим образом: каждое xi a смежно с b , a смежно с b , а смежно с каждым y j . Тогда γ( G ) = 2, поскольку { a , b } — наименьшее доминирующее множество. Если p q , то я ( G ) = p + 1, поскольку — наименьшее доминирующее множество, которое также является независимым (это наименьшее максимальное независимое множество).

Существуют семейства графов, в которых γ( G ) = i ( G ) , то есть каждое минимальное максимальное независимое множество является минимальным доминирующим множеством. Например, γ( G ) = i ( G ), если G граф без когтей . [6]

Граф G называется совершенным по доминированию графом если γ ( H ) = i ( H ) в каждом индуцированном подграфе H графа G. , Поскольку индуцированный подграф графа без клешней является свободным от клешней, отсюда следует, что каждый граф без клешней также совершенен по доминированию. [7]

Для любого графа G его линейный граф L ( G ) не имеет когтей, и, следовательно, минимальное максимальное независимое множество в L ( G ) также является минимальным доминирующим множеством в L ( G ) . Независимый набор в L ( G ) соответствует паросочетанию в G , а доминирующий набор в L ( G ) соответствует множеству ребром в G. с доминирующим Следовательно, минимальное максимальное паросочетание имеет тот же размер, что и минимальное множество с доминирующим ребром.

Доминирование независимых наборов

[ редактировать ]

Число доминирования независимости ( G ) графа G является максимальным среди всех независимых множеств из G наименьшего множества, доминирующего над A. A [8] Для доминирования подмножеств вершин требуется потенциально меньше вершин, чем для доминирования всех вершин, поэтому ( G ) ≤ γ ( G ) для всех G. графов

Неравенство может быть строгим — существуют графы G , для которых ( G ) < γ ( G ) . Например, для некоторого целого числа n пусть G будет графом, в котором вершины являются строками и столбцами доски размером n x n , и две такие вершины связаны тогда и только тогда, когда они пересекаются. Единственными независимыми множествами являются наборы, состоящие только из строк, или наборы, состоящие только из столбцов, и в каждом из них может доминировать одна вершина (столбец или строка), поэтому ( G ) = 1 . Однако, чтобы доминировать над всеми вершинами, нам нужна хотя бы одна строка и один столбец, поэтому γ ( G ) = 2 . Более того, отношение между γ ( G )/ ( G ) может быть сколь угодно большим. Например, если все вершины G являются подмножествами квадратов доски размером n x n , то все равно ( G ) = 1 , но γ ( G ) = n . [8]

Двунезависимое число доминирования iγi ( G ) графа G является максимальным среди всех независимых множеств A из G наименьшего независимого множества, доминирующего A. над выполняются следующие соотношения Для любого графа G :

Проблема доминирования изучалась с 1950-х годов, но темпы исследований доминирования значительно возросли в середине 1970-х годов. В 1972 году Ричард Карп доказал, задача о покрытии множеств что NP-полна . Это имело немедленные последствия для проблемы доминирующего множества, поскольку между двумя задачами существуют простые вершины, которые нужно установить, и ребра, ведущие к биекциям непересекающихся пересечений. является NP-полной . Это доказало, что задача о доминирующем множестве также [9]

Алгоритмы и вычислительная сложность

[ редактировать ]

Проблема покрытия множеств — хорошо известная NP-трудная задача — решающая версия покрытия множеств была одной из 21 NP-полной задачи Карпа . Существует пара L-редукций за полиномиальное время между проблемой минимального доминирующего множества и проблемой покрытия множества . [10] Эти сокращения ( см. ниже ) показывают, что эффективный алгоритм для задачи о минимальном доминирующем множестве обеспечит эффективный алгоритм для задачи о покрытии множества, и наоборот. Более того, сокращения сохраняют коэффициент аппроксимации : для любого α алгоритм α-аппроксимации с полиномиальным временем для минимальных доминирующих наборов обеспечит алгоритм α-аппроксимации с полиномиальным временем для задачи покрытия множества, и наоборот. Обе задачи на самом деле являются Log-APX-полными . [11]

Аппроксимируемость покрытия множеств также хорошо понятна: логарифмический коэффициент аппроксимации можно найти с помощью простого жадного алгоритма , а нахождение сублогарифмического коэффициента аппроксимации NP-трудно. Точнее, жадный алгоритм обеспечивает коэффициент 1 + log| В | аппроксимация минимального доминирующего набора, и ни один алгоритм с полиномиальным временем не может достичь коэффициента аппроксимации лучше, чем c log| В | для некоторого c > 0, если только P = NP . [12]

L-сокращения

[ редактировать ]

Следующие две редукции показывают, что проблема минимального доминирующего множества и проблема покрытия множества эквивалентны относительно L-редукций : учитывая пример одной проблемы, мы можем построить эквивалентный экземпляр другой проблемы. [10]

От доминирующего набора к покрытию набора

[ редактировать ]

Учитывая граф G = ( V , E ) с V = {1, 2, ..., n }, постройте экземпляр покрытия множества ( U , S ) следующим образом: вселенная U - это V , а семейство подмножеств - это S = { S 1 , S 2 , ..., S n } такой, что S v состоит из вершины v и всех смежных с v вершин в G .

Теперь, если D является доминирующим множеством для G , то C = { S v : v D } является допустимым решением проблемы покрытия множества с | С | = | Д | . И наоборот, если C = { S v : v D } — допустимое решение проблемы покрытия множества, то D — доминирующее множество для G , причем | Д | = | С | .

Следовательно, размер минимального доминирующего множества для G равен размеру покрытия минимального множества для ( U , S ) . Более того, существует простой алгоритм, который отображает доминирующее множество в покрытие множества того же размера и наоборот. В частности, эффективный алгоритм α-аппроксимации для покрытия множеств обеспечивает эффективный алгоритм α-аппроксимации для минимальных доминирующих множеств.

Например, учитывая граф G, показанный справа, мы создаем экземпляр покрытия множества с универсумом U = {1, 2, ..., 6} и подмножествами S 1 = {1, 2, 5}, S 2 = {1, 2, 3, 5}, S 3 = {2, 3, 4, 6}, S 4 = {3, 4}, S 5 = {1, 2, 5, 6} и S 6 = {3, 5, 6}. В этом примере D = {3, 5} является доминирующим множеством для G – это соответствует покрытию множества C = { S 3 , S 5 }. Например, вершина 4 € V доминирует вершиной 3 € D , а элемент 4 € U содержится в множестве S 3 C .

От покрытия сета к доминированию сета

[ редактировать ]

Пусть ( S , U ) — пример задачи покрытия множеств с универсумом U и семейством подмножеств S = { S i : i I }; мы предполагаем, что U и набор индексов I не пересекаются. Постройте граф G = ( V , E ) следующим образом: множество вершин равно V = I U существует ребро { i , j } ∈ E , между каждой парой i , j I , а также существует ребро { я , ты } для каждого я I и ты S я . То есть G расщепленный граф : I клика , а U независимое множество .

Теперь, если C = { S i : i D } — допустимое решение проблемы покрытия множеств для некоторого подмножества D I , то D — доминирующее множество для G , причем | Д | = | С | , для каждого u U существует i D такой, что u Si : Во- первых , и по построению u и i смежны в G ; следовательно, над вами доминирует я . Во-вторых, поскольку D должен быть непустым, каждое i I смежно с вершиной в D .

Обратно, пусть D — доминирующее множество для G . Тогда можно построить другое доминирующее множество X такое, что | Х | ≤ | Д | и X I замените каждый u D U соседом i I u : просто . Тогда C = { S i : i X } является допустимым решением задачи покрытия множества, причем | С | = | Х | ≤ | Д | .

На иллюстрации справа показана конструкция для U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { а , б }, S3 d { б , с , d } и S4 , = { с , } = е .
В этом примере C = { S 1 , S 4 } является покрытием множества; это соответствует доминирующему множеству D = {1, 4}.
D = { a , 3, 4} еще одно доминирующее множество графа G. — Учитывая D , мы можем построить доминирующее множество X = {1, 3, 4}, которое не больше D является подмножеством I. и которое Доминирующему множеству X соответствует покрытие множества C = { S 1 , S 3 , S 4 }.

Особые случаи

[ редактировать ]

Если граф имеет максимальную степень Δ, то жадный алгоритм аппроксимации находит O (log Δ) -аппроксимацию минимального доминирующего множества. Кроме того, пусть d g — мощность доминирующего множества, полученная с использованием жадной аппроксимации, тогда справедливо следующее соотношение: , где N — количество узлов, а M — количество ребер в данном неориентированном графе. [13] Для фиксированного Δ это квалифицируется как доминирующий набор для в APX членства ; фактически, он APX-полный. [14]

Задача допускает схему аппроксимации полиномиального времени (PTAS) для особых случаев, таких как единичные дисковые графы и плоские графы . [15] Минимальный доминирующий набор можно найти за линейное время в последовательно-параллельных графах . [16]

Точные алгоритмы

[ редактировать ]

Минимальное доминирующее множество n -вершинного графа можно найти за время O (2 н n ) путем проверки всех подмножеств вершин. Фомин, Грандони и Крач (2009) показывают, как найти минимальное доминирующее множество за время O (1,5137) . н ) и экспоненциальном пространстве, и во времени O (1,5264 н ) и полиномиальное пространство. Более быстрый алгоритм, использующий O (1,5048 н ) время было найдено ван Роой, Недерлофом и ван Дейком (2009) , которые также показали, что за это время можно вычислить количество минимальных доминирующих множеств. Число минимальных доминирующих наборов не превосходит 1,7159. н и все такие наборы можно перечислить за время O (1,7159 н ) . [17]

Параметризованная сложность

[ редактировать ]

Поиск доминирующего множества размера k играет центральную роль в теории параметризованной сложности. Это наиболее известная задача, полная для класса W[2] , которая используется во многих редукциях, чтобы показать неразрешимость других задач. В частности, проблема неразрешима при фиксированных параметрах в том смысле, что ни один алгоритм со временем выполнения f ( k ) n О(1) для любой функции f существует, если W-иерархия не схлопывается до FPT=W[2].

С другой стороны, если входной граф является плоским, задача остается NP-сложной, но алгоритм с фиксированными параметрами известен. Фактически, задача имеет ядро ​​линейного по k размера : [18] а время работы, экспоненциальное по k и кубическое по n, может быть получено путем применения динамического программирования к ветвящемуся разложению ядра. [19] В более общем смысле, проблема доминирующего набора и многие варианты проблемы решаются с фиксированным параметром, если они параметризованы как размером доминирующего набора, так и размером наименьшего запрещенного полного двудольного подграфа ; то есть проблема заключается в FPT на графах без биклик , очень общем классе разреженных графов, включающем планарные графы. [20]

Дополнительный набор к доминирующему множеству, неблокирующий , может быть найден с помощью алгоритма с фиксированными параметрами на любом графе. [21]

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Гэри и Джонсон (1979) .
  2. ^ Вест (2001) , Раздел 3.1.
  3. ^ Класинг и Лафорест (2004) .
  4. ^ Фёрстер (2013) .
  5. ^ Мешулам, Рой (1 мая 2003 г.). «Числа доминирования и гомологии» . Журнал комбинаторной теории, серия А. 102 (2): 321–330. дои : 10.1016/S0097-3165(03)00045-1 . ISSN   0097-3165 .
  6. ^ Аллан и Ласкар (1978) .
  7. ^ Фаудри, Фландрин и Риячек (1997) .
  8. ^ Jump up to: а б Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267. дои : 10.1007/s00493-007-2086-y . ISSN   1439-6912 . S2CID   43510417 .
  9. ^ Хедетниеми и Ласкар (1990) .
  10. ^ Jump up to: а б Джан (1992) , стр. 108–109.
  11. ^ Эскофье и Пашос (2006) .
  12. ^ Raz & Safra (1997) .
  13. ^ Парех (1991) .
  14. ^ Пападимитриу и Яннакакис (1991) .
  15. ^ Крещенци и др. (2000) .
  16. ^ Такамизава, Нисидзеки и Сайто (1982) .
  17. ^ Fomin et al. (2008) .
  18. ^ Альбер, Fellows & Niedermeier (2004) .
  19. ^ Фомин и Тиликос (2006) .
  20. ^ Телле и Вилланджер (2012) .
  21. ^ Дене и др. (2006) .

Дальнейшее чтение

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b61096524fd069b8c4fba33fbfa16adf__1721270460
URL1:https://arc.ask3.ru/arc/aa/b6/df/b61096524fd069b8c4fba33fbfa16adf.html
Заголовок, (Title) документа по адресу, URL1:
Dominating set - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)