Приложения Vertex Cover в реальном мире

22

Какие приложения есть в Vertex Cover Problem в реальном мире?

В каких отраслевых или исследовательских проектах используется фактически внедренное программное обеспечение, основанное на теоретических результатах для задачи Vertex Cover? В частности, реализованы ли какие-либо из следующих теоретических результатов в используемом программном обеспечении?

  • Аппроксимационные алгоритмы для покрытия вершин
  • Алгоритмы экспоненциального времени для Vertex Cover
  • Трактируемые алгоритмы с фиксированными параметрами для Vertex Cover
  • Алгоритмы кернелизации для Vertex Cover
ds.algorithms graph-theory graph-algorithms Scatman
источник
6
один из хороших примеров - в вики о состоянии гонки: en.wikipedia.org/wiki/Vertex_cover#Examples Также в качестве мотивации люди приводят пример мониторинга. В каждой вершине решения мы держим монитор. Я лично думаю, что поиск этого ответа - лучший вариант, чем задавать его здесь.
singhsumit
5
Почему вы думаете, что у вершинного покрытия есть реальные приложения?
Юкка Суомела
3
Я предполагаю, что ответ заключается в том, что покрытия вершин не имеют значительных применений. Но люди изучают их, потому что вершинные покрытия являются простым частным случаем задачи о множественном покрытии. Набор крышек есть приложения. И вы не сможете по-настоящему понять вычислительную сложность проблемы покрытия множеств, если сначала не поймете простые (и не очень простые) особые случаи, такие как покрытия вершин, покрытия ребер, доминирующие множества и т. Д.
Юкка Суомела
3
Как отмечено на en.wikipedia.org/wiki/Vertex_cover#Properties, вершины, не входящие в наименьшее покрытие вершин, образуют наибольший независимый набор, так что по сути это одна и та же проблема. Существует много реальных применений проблемы независимых множеств, например, потому что каждая проблема удовлетворения ограничений может быть непосредственно сведена к ней.
Андрас Саламон
5
@ Андрас: Это хороший момент, но соответствие имеет место только для наименьшего покрытия вершин и наибольшего независимого множества. С точки зрения точных алгоритмов, это по сути одна и та же проблема, но если мы заинтересованы в эффективных алгоритмах, мы обычно довольствуемся какими-то приближениями. И тогда оказывается, что проблема покрытия вершин имеет уникальные свойства, которые не являются общими с проблемой независимых множеств. Мой любимый пример - распределенные вычисления: для небольших вершинных покрытий не требуется нарушение симметрии, для больших независимых наборов это требуется.
Юкка Суомела

Ответы:

13

Некоторые проблемы в области вычислительной биологии кажутся подходящими для практических приложений, которые не являются искусственными - или, по крайней мере, не такими искусственными, как проблемы, упомянутые Юккой Суомела.

Например, люди часто упоминают работу Ф. Абу-Хзама, Р. Коллинза, М. Феллоуза, М. Лэнгстона, В. Сутерса С. Саймонса, Алгоритмы кернелизации для проблемы покрытия вершин: теория и эксперименты , материалы шестого Семинар по разработке алгоритмов и экспериментам (ALENEX), ACM / SIAM, Proc. Прикладная математика 115, 2004.

Как утверждают авторы: «Одно из применений, к которому мы применили наши методы, включает в себя поиск филогенетических деревьев на основе информации о доменных доменах ...» (раздел 8 вышеупомянутой статьи).

Подгруппа авторов имеет аналогичные статьи по этой теме, см., Например, Фейсал Н. Абу-Хзам, Майкл А. Лэнгстон, Пушкар Шанбхаг и Кристофер Т. Саймонс, Масштабируемые параллельные алгоритмы для задач FPT , Algorithmica, том 45, номер 3 269-284.

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

Александр Лангер
источник
4
«По крайней мере, не так искусственно, как проблемы, упомянутые Юккой Суомела», - и я старался быть осторожным, чтобы не упомянуть здесь никаких проблем!
Юкка Суомела
9

Примером может быть то, что края графика представляют дороги, а вершины представляют перекрестки. Задача состоит в том, чтобы разместить камеры видеонаблюдения на перекрестке таким образом, чтобы вы могли видеть весь город, но для экономии средств желательно использовать как можно меньше камер.

galbarm
источник
21
Проблема таких примеров в том, что они, как правило, являются игрушечными примерами. Их можно использовать для иллюстрации определения, но я не думаю, что можно найти ссылки на примеры из реальной жизни, где люди фактически выбирали места расположения камер безопасности, находя минимальное покрытие вершин. Реальные проблемы, подобные этой, имеют тенденцию иметь дополнительные ограничения, многие из которых даже не определены четко, а решения, как правило, жадные и постепенные (сначала установите пару камер безопасности в наиболее критических местах, а затем установите еще несколько когда мы получим больше средств).
Юкка Суомела
Я бы немного отодвинул возражения Юкки. Полезно выявить проблему в основной части, которая является сложной в вычислительном или концептуальном плане. Несмотря на все дополнительные ограничения реального мира, я думаю, что основная сложность вычислений при выборе камер для охвата пространства в реальном мире, по сути, является проблемой покрытия вершин. Конечно, в этом случае алгоритм приближения вполне подходит; найти лучшее покрытие вершин не обязательно. И в этом случае графики будут довольно простыми, возможно, плоскими, например.
6005
8

Вы также можете взглянуть на http://www.dharwadker.org/pirzada/applications/ . Это о приложениях теории графов. В нем также указаны некоторые приложения для покрытия вершин, например, в биохимии и решении проблемы сборки SNP или проблемы безопасности компьютерной сети.

saeedn
источник
1

Мне было несколько удивительно, что минимальное покрытие вершин является подзадачей венгерского алгоритма , а именно, при определении минимального набора горизонтальных или вертикальных линий, которые покрывают все нули, которые были получены путем вычитания минимумов строк и столбцов.

Это равносильно нахождению минимального покрытия вершин в двудольном графе, что также удивительно, может быть решено за полиномиальное время, хорошо описанное здесь

Манфред Вейс
источник
0

Покрытие вершин (точнее, его различные вычисления / приближения) было основным алгоритмическим движком в нашей статье о классификации ближайших соседей: http://ieeexplore.ieee.org/document/6867374/

Арье
источник