Набор дуг обратной связи - Feedback arc set

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

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

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

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

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

Пример

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

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

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

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

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

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

Теоретические результаты

Эта проблема особенно трудна в k-ребристые графы для больших k, где каждое ребро попадает в разные циклы. Вариант решения проблемы, который НП-полный, спрашивает, можно ли разорвать все циклы, удалив не более 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]

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Имеется ли проблема с дугой обратной связи? алгоритм аппроксимации с постоянным коэффициентом аппроксимации?
(больше нерешенных задач по математике)

Если входные орграфы ограничены турниры, возникающая проблема известна как Задача минимальной обратной связи на турнирах (БЫСТРЫЙ). Эта ограниченная проблема допускает схема полиномиальной аппроксимации, и это все еще справедливо для ограниченно взвешенной версии проблемы.[15] Субэкспоненциальный алгоритм с фиксированными параметрами для взвешенного FAST был дан Карпинский и Шуди (2010).[16]

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

Приближения

Несколько аппроксимационные алгоритмы для проблемы были разработаны[17] - включая Рандомизированный алгоритм Монте-Карло что решает проблему в полиномиальное время с произвольным вероятность.[18] Особенно простой алгоритм выглядит следующим образом:

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

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

Рекомендации

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