Связное доминирующее множество

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

Определения

Связное доминирующее множество графа G — это множество D вершин с двумя свойствами:

  1. Из любого узла в D можно перейти в любой другой узел в D по пути, полностью находящемся внутри D. То есть D порождает связный подграф графа G.
  2. Любая вершина в G либо принадлежит D, либо смежна с вершиной из D. То есть D является доминирующим множеством графа G.

Наименьшее связное доминирующее множество[1] графа G — это связное доминирующее множество с наименьшей мощностью среди всех связных доминирующих множеств графа G. Число связного доминирования графа G — это число вершин в наименьшем связном доминирующем множестве[2].

Любое остовное дерево T графа G имеет по меньшей мере два листа. Остовное дерево с максимальной листвой — это остовное дерево, имеющее максимально возможное число листьев среди всех остовных деревьев графа G. Максимальное число листьев графа G — это число листьев в остовном дереве с максимальной листвой[3].

Дополнительность

Если d является числом связного доминирования графа G с n вершинами, где n > 2, и l — его максимальное число листьев, то три величины d, l и n связаны простым равенством

[4].

Если D является связным доминирующим множеством, то существует остовное дерево в G, листья которого включают все вершины, не находящиеся в D — образуем остовное дерево подграфа, порождённого множеством D вместе с рёбрами, соединяющими каждую оставшуюся вершину v, не лежащую в D, с соседней v вершиной, принадлежащей D. Это показывает, что l ≥ n − d.

В обратном направлении, если T — любое остовное дерево в G, то нелистовые вершины в дереве T образуют связное доминирующее множество графа G. Это показывает, что n − l ≥ d. из этих двух полученных неравенств следует равенство n=d + l.

Таким образом, в любом графе сумма числа связного доминирования и максимального числа листьев равна числу вершин графа. С вычислительной точки зрения это означает, что вычисление числа связного доминирования имеет ту же трудность, что и вычисление максимального числа листьев.

Алгоритмы

Задача проверки, существует ли связное доминирующее множество с размером, меньшим заданного порога, NP-полна, а такая задача эквивалентна проверке, существует ли остовное дерево, имеющее число листьев не меньше заданного. Таким образом можно полагать, что задачу нахождения минимального связного доминирующего множества и задачу поиска остовного дерева с максимальным числом листьев нельзя решить за полиномиальное время.

Если рассматривать задачи в терминах аппроксимационных алгоритмов, связное доминирование и максимальная листва остовных деревьев не то же самое — аппроксимация одной задачи с данным аппроксимационным коэффициентом не то же самое, что аппроксимация другой задачи с тем же коэффициентом. Существует аппроксимация для задачи поиска наименьшего связного доминирующего множества с коэффициентом 2 ln Δ + O(1), где Δ означает максимальную степень вершин в графе G[5]. Задача нахождения остовного дерева с максимальной листвой MAX-SNP трудна, откуда следует, что, по всей видимости, не существует приближенной схемы полиномиального времени[6]. Однако задачу можно аппроксимировать с коэффициентом 2 за полиномиальное время[7].

Обе задачи можно решить на графах с n вершинами за время O(1.9n)[8]. Задача о максимальной листве фиксированно-параметрически разрешима, что означает — её можно решить за время, экспоненциально зависящее от числа листьев, но лишь полиномиально от размера графа. Клам-значение этих алгоритмов (интуитивно, это число листьев, для которого алгоритм работает приемлемое время) постепенно выросло по мере улучшения алгоритмов примерно до 37[9] и есть предположения, что значение 50 можно достичь[10].

Приложения

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

Максимальное число листьев используется для разработки фиксированно-параметрически разрешимых алгоритмов — некоторые NP-трудные задачи оптимизации можно решить за полиномиальное время на графах с ограниченным максимальным числом листьев[3].

См. также
  • Универсальная вершина, вершина, которая (если таковая существует) даёт минимальное связное доминирующее множество размера 1

Примечания
  1. Часто встречается Минимальное связное доминирующее множество. В русскоязычной литературе наблюдается большая путаница слов максимальный и наибольший (соответственно, минимальный и наименьший). Обычно под максимальным понимается элемент, который нельзя расширить, а под наибольшим понимается элемент с максимальной числовой характеристикой (сравните, например, максимальное паросочетание и наибольшее паросочетание)
  2. Sampathkumar, Walikar, 1979, с. 607–613.
  3. Fellows, Lokshtanov, Misra и др., 2009, с. 822–848.
  4. Douglas, 1992, с. 41–47.
  5. Guha, Khuller, 1998, с. 374–387.
  6. Galbiati, Maffioli, Morzenti1994, с. 45–49.
  7. Solis-Oba, 1998, с. 441–452.
  8. Fernau, Kneis, Kratsch и др., 2011, с. 6290–6302.
  9. Binkele-Raible, Fernau, 2014, с. 179–200.
  10. Fellows, McCartin, Rosamond, Stege, 2000, с. 240–251.
  11. Wu, Li, 1999, с. 7–14.

Литература
  • Sampathkumar E., Walikar H.B. The connected domination number of a graph // J. Math. Phys. Sci. — 1979. — Т. 13, вып. 6. — С. 607–613.
  • Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances Rosamond, Saket Saurabh. The complexity ecology of parameters: an illustration using bounded max leaf number // Theory of Computing Systems. — 2009. — Т. 45, вып. 4. — С. 822–848. — doi:10.1007/s00224-009-9167-9.
  • Robert J. Douglas. NP-completeness and degree restricted spanning trees // Discrete Mathematics. — 1992. — Т. 105, вып. 1–3. — С. 41–47. — doi:10.1016/0012-365X(92)90130-8.
  • Guha S., Khuller S. Approximation algorithms for connected dominating sets // Algorithmica. — 1998. — Т. 20, вып. 4. — С. 374–387. — doi:10.1007/PL00009201.
  • Galbiati G., Maffioli F., Morzenti A. A short note on the approximability of the maximum leaves spanning tree problem // Information Processing Letters. — 1994. — Т. 52, вып. 1. — С. 45–49. — doi:10.1016/0020-0190(94)90139-2.
  • Roberto Solis-Oba. 2-approximation algorithm for finding a spanning tree with maximum number of leaves // Proc. 6th European Symposium on Algorithms (ESA'98). — Springer-Verlag, 1998. — Т. 1461. — С. 441–452. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-68530-8_37.
  • Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith. An exact algorithm for the maximum leaf spanning tree problem // Theoretical Computer Science. — 2011. — Т. 412, вып. 45. — С. 6290–6302. — doi:10.1016/j.tcs.2011.07.011.
  • Daniel Binkele-Raible, Henning Fernau. A parameterized measure-and-conquer analysis for finding a k-leaf spanning tree in an undirected graph // Discrete Mathematics & Theoretical Computer Science. — 2014. — Т. 16, вып. 1. — С. 179–200.
  • Michael R. Fellows, Catherine McCartin, Frances A. Rosamond, Ulrike Stege. Coordinatized kernels and catalytic reductions: an improved FPT algorithm for max leaf spanning tree and other problems // FST-TCS 2000: Foundations of Software Technology and Theoretical Computer Science. — Springer, Berlin, 2000. — Т. 1974. — С. 240–251. — (Lecture Notes in Comput. Sci.). — doi:10.1007/3-540-44450-5_19.
  • Wu J., Li H. On calculating connected dominating set for efficient routing in ad hoc wireless networks // Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. — ACM, 1999. — С. 7–14. — doi:10.1145/313239.313261.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.