Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
В этом ориентированном графе нет циклов: из любой вершины (точки) невозможно попасть обратно в ту же точку, следуя связям в направлении, указанном стрелками.

Набор дуг обратной связи ( FAS ) или набор ребер обратной связи - это набор ребер, которые при удалении из графа оставляют ациклический граф. Другими словами, это набор, содержащий хотя бы одно ребро каждого цикла в графе. В теории графов , А ориентированный граф может содержать направленные циклы , замкнутый односторонний путь ребер. В некоторых приложениях такие циклы нежелательны, и мы хотим их устранить и получить ориентированный ациклический граф (DAG). Один из способов сделать это - просто отбросить ребра из графа, чтобы разорвать циклы.

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

Набор дуг с минимальной обратной связью (размер которого нельзя уменьшить путем удаления каких-либо ребер) обладает дополнительным свойством: если ребра в нем переворачиваются, а не удаляются, то граф остается ациклическим. Поиск небольшого набора ребер с этим свойством - ключевой шаг в рисовании многоуровневого графа . [1] [2]

Иногда желательно , чтобы упасть , как несколько ребер , как это возможно, получение набора дуги минимум обратной связи (МФА), или дуально с максимальной ациклический подграф . Это сложная вычислительная задача, для которой было разработано несколько приближенных решений.

Пример [ править ]

В качестве простого примера рассмотрим следующую гипотетическую ситуацию, когда для того, чтобы чего-то добиться, одни вещи должны быть достигнуты раньше других:

  • Ваша цель - получить газонокосилку.
  • Джордж говорит, что даст вам пианино, но только в обмен на газонокосилку.
  • Гарри говорит, что даст вам газонокосилку, но только в обмен на микроволновую печь.
  • Джейн говорит, что даст вам микроволновку, но только в обмен на пианино.

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

Однако предположим, что вы предлагаете Джорджу 100 долларов за его фортепиано. Если он соглашается, это эффективно убирает границу от газонокосилки до пианино, потому что вам больше не нужна газонокосилка, чтобы достать пианино. Следовательно, цикл прерывается, и вы можете дважды торговать, чтобы получить газонокосилку. Это одно ребро составляет набор дуг обратной связи.

Минимальная дуга обратной связи установлена [ править ]

Как и в приведенном выше примере, удаление ребра обычно связано с определенными затратами. По этой причине мы хотели бы удалить как можно меньше краев. Удаление одного ребра достаточно в простом цикле, но в целом определение минимального количества ребер для удаления - это NP-трудная задача, называемая минимальным набором дуг обратной связи или проблемой максимального ациклического подграфа.

Теоретические результаты [ править ]

Эта проблема особенно сложна в k- реберных графах для больших k , где каждое ребро попадает в множество различных циклов. Версия решения проблемы, которая является NP-полной , спрашивает, можно ли разорвать все циклы, удалив не более k ребер; это была одна из 21 NP-полных проблем Ричарда М. Карпа , показанная путем редукции из проблемы вершинного покрытия . [3] [4]

Несмотря на то, что проблема набора дуг обратной связи является NP-полной, проблема множества дуг обратной связи решаема с фиксированными параметрами : существует алгоритм для ее решения, время работы которого является фиксированным полиномом от размера входного графа (независимо от количества ребер в наборе), но экспоненциальным. в количестве ребер в наборе дуг обратной связи. [5] Альтернативно, управляемый алгоритм с фиксированными параметрами задается методом динамического программирования , который зависит только экспоненциально от размерности пространства цикла графа. [6]

Задача минимального набора дуг обратной связи является APX-сложной , что означает, что (при условии, что P ≠ NP ) существует жесткий предел качества его аппроксимации, константа c > 1, так что каждый алгоритм аппроксимации за полиномиальное время иногда возвращает набор ребер большего размера. чем c оптимального размера. Доказательство включает редукции с сохранением аппроксимации от покрытия вершины до набора вершин обратной связи и от набора вершин обратной связи к набору дуг обратной связи. [7] [8] [9]В частности, поскольку вершинное покрытие не имеет приближения лучше, чем 1,3606, если только P ≠ NP, то же самое верно и для набора дуг обратной связи. То есть можно взять c = 1,3606 . [10] Если гипотеза об уникальных играх верна, этот порог неприемлемости может быть увеличен до произвольно близкого к 2. [11]

С другой стороны, наиболее известный алгоритм аппроксимации имеет непостоянный коэффициент аппроксимации O (log n log log n ). [9] [12] Для двойственной задачи аппроксимации максимального числа ребер в ациклическом подграфе возможно приближение несколько лучше, чем 1/2. [13] [14] Определение того, имеет ли набор дуги обратной связи алгоритм аппроксимации с постоянным отношением, или необходимо непостоянное отношение, остается открытой проблемой.

Нерешенная задача по математике :

Имеется ли в задаче набора дуг обратной связи алгоритм аппроксимации с постоянным коэффициентом аппроксимации?

(больше нерешенных задач по математике)

Если входные орграфы ограничены турнирами , результирующая проблема известна как проблема минимального набора дуг обратной связи на турнирах (FAST). Эта ограниченная задача допускает схему аппроксимации за полиномиальное время , и это все еще справедливо для ограниченной взвешенной версии проблемы. [15] Субэкспоненциальный алгоритм с фиксированными параметрами для взвешенного FAST был дан Karpinski & Schudy (2010) . [16]

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

Приближения [ править ]

Было разработано несколько приближенных алгоритмов для этой задачи [17], включая рандомизированный алгоритм Монте-Карло, который решает задачу за полиномиальное время с произвольной вероятностью . [18] Вот особенно простой алгоритм:

  • Зафиксируем произвольную перестановку вершин; то есть пометить вершины от 1 до n , произвольно выбирая, какую вершину присвоить какой метке.
  • Постройте два подграфа L и R , содержащие ребра ( u , v ), где u < v , и те, где u > v , соответственно.

Теперь и L, и R являются ациклическими подграфами G , и хотя бы один из них по крайней мере вдвое меньше максимального ациклического подграфа. [19] : 348

Ссылки [ править ]

  1. ^ Ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1998), «Многослойные рисунки орграфов», Graph Drawing: Algorithms for the Visualization of Graph , Prentice Hall , pp. 265–302, ISBN 9780133016154.
  2. ^ Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки орграфов», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , конспект лекций по информатике, 2025 г. , Springer-Verlag, стр. 87–120, doi : 10.1007 / 3-540-44969-8_5.
  3. ^ Карп, Ричард М. (1972), "Сводимость среди комбинаторных проблем", Сложность компьютерных вычислений , Proc. Симпозиумы. IBM Thomas J. Watson Res. Center, Yorktown Heights, Нью-Йорк, Нью-Йорк: Пленум, стр. 85–103..
  4. ^ Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, A1.1: GT8, p. 192 , ISBN 0-7167-1045-5.
  5. ^ Chen, Jianer; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), "Алгоритм с фиксированными параметрами для задачи о множестве вершин с направленной обратной связью", Журнал ACM , 55 (5): 1–19, doi : 10.1145 / 1411509.1411511.
  6. ^ Хехт, Майкл (2017), "Точные Локализации множеств обратной связи", Теория вычислительных систем , 62 (5): 1048-1084, Arxiv : 1702,07612 , DOI : 10.1007 / s00224-017-9777-6.
  7. ^ Ausiello, Г .; D'Atri, A .; Protasi, М. (1980), "Структура сохранения сокращения среди задач выпуклой оптимизации", журнал компьютерных и системных наук , 21 (1): 136-153, DOI : 10,1016 / 0022-0000 (80) 90046-X , MR 0589808 .
  8. ^ Канн, Вигго (1992), Об аппроксимируемости NP-полных задач оптимизации (PDF) , Ph.D. кандидатская диссертация, Департамент численного анализа и вычислительной техники, Королевский технологический институт, Стокгольм .
  9. ^ a b Крещенци, Пьерлуиджи; Канн, Вигго; Халлдорссон, Магнус; Карпинский, Марек ; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", Сборник проблем оптимизации NP.
  10. ^ Динур, Ирит ; Сафра, Самуэль (2005), "О жесткости аппроксимирующих минимальной вершины крышки" (PDF) , Анналы математики , 162 (1): 439-485, DOI : 10,4007 / annals.2005.162.439 . (Предварительная версия в Динур, Ирит (2002). «Важность предвзятости». Труды тридцать четвертого ежегодного симпозиума ACM по теории вычислений - STOC '02 . Doi : 10.1145 / 509907.509915 ..)
  11. ^ Хот, Субхаш ; Регев, Одед (2008), "Vertex крышка может быть трудно приблизиться к в пределах 2 - е ", журнал компьютерных и системных наук , 74 (3): 335-349, DOI : 10.1016 / j.jcss.2007.06.019 , Руководство по ремонту 2384079 .
  12. ^ Даже, G .; Naor, J .; Schieber, B .; Судан, М. (1998), "Приближающие минимальные наборы обратной связи и multicuts в ориентированных графах", Algorithmica , 20 (2): 151-174, DOI : 10.1007 / PL00009191 , МР 1484534 .
  13. ^ Бергер, Б .; Шор П. (1990), "Алгоритмы аппроксимации для задачи о максимальном ациклическом подграфе", Труды 1-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA'90) , стр. 236–243.
  14. ^ Идс, П .; Lin, X .; Смит, У. Ф. (1993), "Быстрая и эффективная эвристика для задачи о множестве дуг обратной связи" , Письма об обработке информации , 47 (6): 319–323, DOI : 10.1016 / 0020-0190 (93) 90079-O.
  15. ^ Кеньон-Матье, Клэр; Шуди, Уоррен (2007), «Как ранжировать с небольшим количеством ошибок: PTAS для взвешенной обратной связи, установленной на турнирах», Proc. 39 - й ACM симпозиум по теории вычислений (STOC '07) , стр 95-103,. DOI : 10,1145 / 1250790,1250806 , MR 2402432 . См. Также расширенную версию автора .
  16. ^ Карпинский, М .; Schudy, W. (2010), "Более быстрые алгоритмы для турнира по заданной дуге с обратной связью, агрегирования рангов Кемени и турнира промежуточности", Proc. Двадцать первого ИСААК (2010) , Lecture Notes в области компьютерных наук , 6506 , стр 3-14,. Arxiv : 1006,4396 , DOI : 10.1007 / 978-3-642-17517-6_3.
  17. ^ Хассин, Рафаэль; Рубинштейн, Шломи (1994). «Аппроксимации для задачи о максимальном ациклическом подграфе». Письма об обработке информации . 51 (3): 133–140. CiteSeerX 10.1.1.39.7717 . DOI : 10.1016 / 0020-0190 (94) 00086-7 . 
  18. ^ Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные программные вычисления . 41 : 235–246. DOI : 10.1016 / j.asoc.2015.12.018 .
  19. ^ Skiena, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science + Business Media . С. 348, 559–561. ISBN 978-1-849-96720-4.