Ребра, разрешающие все циклы в графе

Введение

Ребра, пересекающие все циклы в графе

В теории графов и алгоритмах на графах, множество обратных дуг (или ребер обратной связи) в ориентированном графе – это подмножество ребер графа, содержащее хотя бы одно ребро из каждого цикла в графе. Удаление этих ребер из графа разрывает все циклы, создавая ациклический подграф исходного графа, часто называемый ориентированным ациклическим графом. Множество обратных дуг с минимальным возможным количеством ребер является минимальным множеством обратных дуг, и его удаление оставляет максимальный ациклический подграф; также используются взвешенные варианты этих задач оптимизации. Если множество обратных дуг минимально, то есть удаление любого ребра из него приводит к подмножеству, которое не является множеством обратных дуг, то оно обладает дополнительным свойством: изменение направления всех его ребер, а не их удаление, приводит к ориентированному ациклическому графу. Множества обратных дуг находят применение в анализе цепей, химической инженерии, разрешении взаимных блокировок, ранжировании при голосовании, ранжировании конкурентов в спортивных мероприятиях, математической психологии, этологии и построении графов. Поиск минимальных множеств обратных дуг и максимальных ациклических подграфов является NP-трудной задачей; её можно решить точно за экспоненциальное время или за время, полиномиально зависящее от фиксированного параметра. За полиномиальное время минимальное множество обратных дуг можно приблизить с точностью до полилогарифмической погрешности, а максимальные ациклические подграфы – с точностью до постоянного множителя. Оба они трудно приблизить точнее, чем с некоторым постоянным множителем, что является результатом неприблизимости, который можно усилить в соответствии с гипотезой об уникальных играх. Для турнирных графов минимальное множество обратных дуг можно приблизить более точно, а для планарных графов обе задачи можно решить точно за полиномиальное время. Тесно связанной задачей является множество вершин обратной связи – это набор вершин, содержащий хотя бы одну вершину из каждого цикла в ориентированном или неориентированном графе. В неориентированных графах остовные деревья являются наибольшими ациклическими подграфами, а количество ребер, удаленных при построении остовного дерева, является рангом цепи.

Приложения

Несколько задач, связанных с поиском рейтингов или упорядочений, можно решить, находя обратный реберный набор на турнирном графе — ориентированном графе, в котором между каждой парой вершин есть одно ребро. Инвертирование ребер обратного реберного набора создает ориентированный ациклический граф, уникальный топологический порядок которого можно использовать в качестве желаемого рейтинга. Применения этого метода включают следующее:
В спортивных соревнованиях с круговой системой проведения игр результаты каждой игры можно записать, направляя ребро от проигравшего к победителю каждой игры. Нахождение минимального обратного реберного набора в полученном графе, инвертирование его ребер и топологическая сортировка позволяют получить рейтинг всех участников. Среди всех возможных способов выбора рейтинга он минимизирует общее количество сенсаций, то есть игр, в которых участник с более низким рейтингом побеждает участника с более высоким рейтингом. Многие виды спорта используют более простые методы для ранжирования в групповых турнирах, основанные на начислении очков за каждую игру; эти методы могут обеспечить постоянную аппроксимацию к минимальному рейтингу с точки зрения числа сенсаций. В приматологии и, в более широком смысле, в этологии иерархии доминирования часто определяются путем поиска упорядочения с наименьшим количеством инверсий в наблюдаемом поведении доминирования, что является еще одной формой задачи о минимальном обратном реберном наборе. В математической психологии представляет интерес определение рейтингов испытуемых наборов объектов в соответствии с заданным критерием, например, их предпочтением или восприятием размера, на основе попарных сравнений между всеми парами объектов. Минимальный обратный реберный набор в турнирном графе обеспечивает рейтинг, который противоречит как можно меньшему числу попарных результатов. В качестве альтернативы, если эти сравнения приводят к независимым вероятностям для каждого попарного упорядочения, то максимальное правдоподобие общего рейтинга можно получить, преобразовав эти вероятности в логарифмические правдоподобия и найдя обратный реберный набор минимального веса в полученном турнире. То же упорядочение с максимальным правдоподобием можно использовать для серирования — задачи в статистике и разведочном анализе данных, заключающейся в упорядочивании элементов в линейный порядок, в случаях, когда имеются данные, обеспечивающие попарные сравнения между элементами. В ранжированном голосовании метод Кемени — Янга можно описать как поиск упорядочения, которое минимизирует сумму, по парам кандидатов, числа избирателей, которые предпочитают противоположное упорядочение для этой пары. Это можно сформулировать и решить как задачу о минимальном обратном реберном наборе, в которой вершины представляют кандидатов, ребра направлены для представления победителя каждого поединка, а стоимость каждого ребра представляет число избирателей, которые были бы недовольны, если бы проигравшему в поединке был присвоен более высокий рейтинг. Еще одним ранним применением обратных реберных наборов было проектирование последовательных логических схем, в которых сигналы могут распространяться по циклам через схему, а не всегда прогрессировать от входов к выходам. В таких схемах минимальный обратный реберный набор характеризует количество точек, в которых необходимо усиление, чтобы сигналы могли распространяться без потери информации. В синхронных схемах, созданных из асинхронных компонентов, синхронизация может быть достигнута путем размещения синхронизирующих вентилей на ребрах обратного реберного набора. Кроме того, разрез схемы по ребрам обратного реберного набора уменьшает оставшуюся схему до комбинационной логики, упрощая ее анализ, а размер обратного реберного набора определяет, сколько дополнительного анализа необходимо для понимания поведения схемы после разреза. Аналогично, в построении блок-схем технологических процессов в химической инженерии, разрыв ребер диаграммы технологического процесса по обратным реберным наборам и перебор всех возможностей для значений на этих ребрах позволяет систематически анализировать остальную часть процесса из-за его ацикличности. В этом приложении идея разрыва ребер таким образом называется «разрывом». При построении слоистых графов вершины заданного ориентированного графа разбиваются на упорядоченную последовательность подмножеств (слои рисунка), и каждое подмножество размещается вдоль горизонтальной линии этого рисунка, при этом ребра простираются вверх и вниз между этими слоями. В этом типе рисунка желательно, чтобы большинство или все ребра были ориентированы последовательно вниз, а не смешивались ребра, направленные вверх и вниз, чтобы отношения достижимости в рисунке были более наглядными. Это достигается путем нахождения минимального или наименьшего обратного реберного набора, инвертирования ребер в этом наборе и последующего выбора разбиения на слои таким образом, чтобы оно соответствовало топологическому порядку полученного ациклического графа. Обратные реберные наборы также использовались для другой подзадачи построения слоистых графов — упорядочивания вершин внутри последовательных пар слоев. При разрешении взаимных блокировок в операционных системах задача удаления наименьшего числа зависимостей для снятия взаимной блокировки может быть смоделирована как задача нахождения минимального обратного реберного набора. Однако из-за вычислительной сложности нахождения этого набора и необходимости скорости в компонентах операционной системы в этом приложении часто используются эвристики, а не точные алгоритмы.

Several problems involving finding rankings or orderings can be solved by finding a feedback arc set on a tournament graph, a directed graph with one edge between each pair of vertices. Reversing the edges of the feedback arc set produces a directed acyclic graph whose unique topological order can be used as the desired ranking. Applications of this method include the following:
In sporting competitions with round robin play, the outcomes of each game can be recorded by directing an edge from the loser to the winner of each game. Finding a minimum feedback arc set in the resulting graph, reversing its edges, and topological ordering, produces a ranking on all of the competitors. Among all of the different ways of choosing a ranking, it minimizes the total number of upsets, games in which a lower ranked competitor beat a higher ranked competitor. Many sports use simpler methods for group tournament ranking systems based on points awarded for each game; these methods can provide a constant approximation to the minimum upset ranking. In primatology and more generally in ethology, dominance hierarchies are often determined by searching for an ordering with the fewest reversals in observed dominance behavior, another form of the minimum feedback arc set problem. In mathematical psychology, it is of interest to determine subjects' rankings of sets of objects according to a given criterion, such as their preference or their perception of size, based on pairwise comparisons between all pairs of objects. The minimum feedback arc set in a tournament graph provides a ranking that disagrees with as few pairwise outcomes as possible. Alternatively, if these comparisons result in independent probabilities for each pairwise ordering, then the maximum likelihood estimation of the overall ranking can be obtained by converting these probabilities into log likelihoods and finding a minimum weight feedback arc set in the resulting tournament. The same maximum likelihood ordering can be used for seriation, the problem in statistics and exploratory data analysis of arranging elements into a linear ordering, in cases where data is available that provides pairwise comparisons between the elements. In ranked voting, the Kemeny–Young method can be described as seeking an ordering that minimizes the sum, over pairs of candidates, of the number of voters who prefer the opposite ordering for that pair. This can be formulated and solved as a minimum weight feedback arc set problem, in which the vertices represent candidates, edges are directed to represent the winner of each head to head contest, and the cost of each edge represents the number of voters who would be made unhappy by giving a higher ranking to the head to head loser. Another early application of feedback arc sets concerned the design of sequential logic circuits, in which signals can propagate in cycles through the circuit instead of always progressing from inputs to outputs. In such circuits, a minimum feedback arc set characterizes the number of points at which amplification is necessary to allow the signals to propagate without loss of information. In synchronous circuits made from asynchronous components, synchronization can be achieved by placing clocked gates on the edges of a feedback arc set. Additionally, cutting a circuit on a feedback arc a set reduces the remaining circuit to combinational logic, simplifying its analysis, and the size of the feedback arc set controls how much additional analysis is needed to understand the behavior of the circuit across the cut. Similarly, in process flowsheeting in chemical engineering, breaking edges of a process flow diagram on a feedback arc set, and guessing or trying all possibilities for the values on those edges, allows the rest of the process to be analyzed in a systematic way because of its acyclicity. In this application, the idea of breaking edges in this way is called "tearing". In layered graph drawing, the vertices of a given directed graph are partitioned into an ordered sequence of subsets (the layers of the drawing), and each subset is placed along a horizontal line of this drawing, with the edges extending upwards and downwards between these layers. In this type of drawing, it is desirable for most or all of the edges to be oriented consistently downwards, rather than mixing upwards and downwards edges, in order for the reachability relations in the drawing to be more visually apparent. This is achieved by finding a minimum or minimal feedback arc set, reversing the edges in that set, and then choosing the partition into layers in a way that is consistent with a topological order of the resulting acyclic graph. Feedback arc sets have also been used for a different subproblem of layered graph drawing, the ordering of vertices within consecutive pairs of layers. In deadlock resolution in operating systems, the problem of removing the smallest number of dependencies to break a deadlock can be modeled as one of finding a minimum feedback arc set. However, because of the computational difficulty of finding this set, and the need for speed within operating system components, heuristics rather than exact algorithms are often used in this application.

Эквивалентность

Набор минимальных дуг обратной связи и максимальный ациклический подграф эквивалентны для целей точной оптимизации, поскольку один является дополнением к другому. Однако для параметризованной сложности и аппроксимации они различаются, потому что анализ, используемый для этих типов алгоритмов, зависит от размера решения, а не только от размера входного графа, и минимальный набор дуг обратной связи и максимальный ациклический подграф имеют разные размеры. Набор дуг обратной связи данного графа эквивалентен набору вершин обратной связи его линейного графа. Здесь набор вершин обратной связи определяется аналогично набору дуг обратной связи как подмножество вершин графа, удаление которого устранит все циклы. Линейный граф направленного графа имеет вершину для каждого ребра в , и ребро для каждой пары последовательных ребер в . В обратном направлении, минимальный набор вершин обратной связи данного графа может быть получен из решения задачи о минимальном наборе дуг обратной связи на графе, полученном путем разбиения каждой вершины в на две вершины: одну для входящих ребер и одну для исходящих ребер. Эти преобразования позволяют преобразовывать точные алгоритмы для наборов дуг обратной связи и для наборов вершин обратной связи друг в друга с соответствующей корректировкой границ их сложности. Однако это преобразование не сохраняет качество аппроксимации для задачи о максимальном ациклическом подграфе. Как в точных, так и в приближенных решениях задачи о наборе дуг обратной связи, достаточно независимо решать каждую сильно связную компоненту данного графа и далее разбивать эти сильно связные компоненты на бисвязные компоненты, разделяя их в вершинах артикуляции. Выбор решения в рамках любой из этих подзадач не влияет на другие, и ребра, которые не встречаются ни в одной из этих компонент, бесполезны для включения в набор дуг обратной связи. Если одна из этих компонент может быть разделена на два несвязных подграфа удалением двух вершин, применяется более сложное разложение, позволяющее разбить проблему на подзадачи, полученные из трисвязных компонент ее сильно связных компонент.

The minimum feedback arc set and maximum acyclic subgraph are equivalent for the purposes of exact optimization, as one is the complement set of the other. However, for parameterized complexity and approximation, they differ, because the analysis used for those kinds of algorithms depends on the size of the solution and not just on the size of the input graph, and the minimum feedback arc set and maximum acyclic subgraph have different sizes from each other. A feedback arc set of a given graph is the same as a feedback vertex set of a directed line graph of Here, a feedback vertex set is defined analogously to a feedback arc set, as a subset of the vertices of the graph whose deletion would eliminate all cycles. The line graph of a directed graph has a vertex for each edge of , and an edge for each two edge path in In the other direction, the minimum feedback vertex set of a given graph can be obtained from the solution to a minimum feedback arc set problem on a graph obtained by splitting every vertex of into two vertices, one for incoming edges and one for outgoing edges. These transformations allow exact algorithms for feedback arc sets and for feedback vertex sets to be converted into each other, with an appropriate translation of their complexity bounds. However, this transformation does not preserve approximation quality for the maximum acyclic subgraph problem. In both exact and approximate solutions to the feedback arc set problem, it is sufficient to solve separately each strongly connected component of the given graph, and to break these strongly connected components down even farther to their biconnected components by splitting them at articulation vertices. The choice of solution within any one of these subproblems does not affect the others, and the edges that do not appear in any of these components are useless for inclusion in the feedback arc set. When one of these components can be separated into two disconnected subgraphs by removing two vertices, a more complicated decomposition applies, allowing the problem to be split into subproblems derived from the triconnected components of its strongly connected components.

Точно .

Один из способов найти минимальный набор дуг обратной связи — это поиск упорядочения вершин, при котором как можно меньше рёбер направлено от более поздних вершин к более ранним в этом упорядочении. Поиск всех перестановок графа из *n* вершин займёт время *n!*, но метод динамического программирования, основанный на алгоритме Хелда — Карпа, может найти оптимальную перестановку за время *O(n²2ⁿ)*, также используя экспоненциальное количество памяти. Алгоритм «разделяй и властвуй», который проверяет все разбиения вершин на два равных подмножества и рекурсивно применяется к каждому подмножеству, может решить задачу за время *O(n³)*, используя полиномиальное пространство. В параметризованной сложности время работы алгоритмов измеряется не только в терминах размера входного графа, но и в терминах отдельного параметра графа. В частности, для задачи о минимальном наборе дуг обратной связи так называемым естественным параметром является размер минимального набора дуг обратной связи. Для графов с *n* вершинами и естественным параметром *k*, задача о наборе дуг обратной связи может быть решена за время *2ᴼ(kⁿ)*, путём сведения её к эквивалентной задаче о наборе вершин обратной связи и применения параметризованного алгоритма для набора вершин обратной связи. Поскольку показатель *n* в этом алгоритме является константой, не зависящей от *k*, этот алгоритм называется фиксированным параметром, обрабатываемым. Также изучались и другие параметры, отличные от естественного. Алгоритм с фиксированным параметром, использующий динамическое программирование, может найти минимальные наборы дуг обратной связи за время *O(cᵏ)*, где *c* — ранг цепи базового неориентированного графа. Ранг цепи — это неориентированный аналог набора дуг обратной связи, минимальное количество рёбер, которые необходимо удалить из графа, чтобы привести его к остовного дерева; его гораздо легче вычислить, чем минимальный набор дуг обратной связи. Для графов с шириной дерева *w*, динамическое программирование на дереве разложения графа может найти минимальный набор дуг обратной связи за время, полиномиальное по размеру графа и экспоненциальное по *w*. В соответствии с гипотезой об экспоненциальном времени, лучшая зависимость от *w* невозможна. Вместо минимизации размера набора дуг обратной связи, исследователи также рассматривали минимизацию максимального количества рёбер, удалённых из любой вершины. Эта вариация задачи может быть решена за линейное время. Все минимальные наборы дуг обратной связи могут быть перечислены алгоритмом с полиномиальной задержкой на каждый набор.

One way to find the minimum feedback arc set is to search for an ordering of the vertices such that as few edges as possible are directed from later vertices to earlier vertices in the ordering. Searching all permutations of an vertex graph would take time , but a dynamic programming method based on the Held–Karp algorithm can find the optimal permutation in time , also using an exponential amount of space. A divide and conquer algorithm that tests all partitions of the vertices into two equal subsets and recurses within each subset can solve the problem in time , using polynomial space. In parameterized complexity, the time for algorithms is measured not just in terms of the size of the input graph, but also in terms of a separate parameter of the graph. In particular, for the minimum feedback arc set problem, the so called natural parameter is the size of the minimum feedback arc set. On graphs with vertices, with natural parameter , the feedback arc set problem can be solved in time , by transforming it into an equivalent feedback vertex set problem and applying a parameterized feedback vertex set algorithm. Because the exponent of in this algorithm is the constant , independent of , this algorithm is said to be fixed parameter tractable. Other parameters than the natural parameter have also been studied. A fixed parameter tractable algorithm using dynamic programming can find minimum feedback arc sets in time , where is the circuit rank of the underlying undirected graph. The circuit rank is an undirected analogue of the feedback arc set, the minimum number of edges that need to be removed from a graph to reduce it to a spanning tree; it is much easier to compute than the minimum feedback arc set. For graphs of treewidth , dynamic programming on a tree decomposition of the graph can find the minimum feedback arc set in time polynomial in the graph size and exponential in Under the exponential time hypothesis, no better dependence on is possible. Instead of minimizing the size of the feedback arc set, researchers have also looked at minimizing the maximum number of edges removed from any vertex. This variation of the problem can be solved in linear time. All minimal feedback arc sets can be listed by an algorithm with polynomial delay per set.

Ограниченные входы

В направленных плоских графах задача о наборе дуг обратной связи двойственна задаче сжатия набора ребер (диоинов) для получения сильно связного графа. Эта двойственная задача разрешима за полиномиальное время, и, следовательно, разрешима и задача о минимальном наборе дуг обратной связи для плоских графов. Взвешенная версия задачи может быть решена за , а когда веса – положительные целые числа, не превышающие число , – за . Эти алгоритмы для плоских графов можно расширить на графы, не имеющие графа полезности в качестве минора, используя тот факт, что трисвязные компоненты этих графов либо плоские, либо имеют ограниченный размер. Плоские графы также были обобщены другим способом, в класс направленных графов, называемых слабо ациклическими диграфами, определяемыми целочисленностью определенного политопа, связанного с их наборами дуг обратной связи. Любой плоский направленный граф в этом смысле является слабо ациклическим, и задача о наборе дуг обратной связи может быть решена за полиномиальное время для всех слабо ациклических диграфов. Графы редуктивного потока – это еще один класс направленных графов, для которых задача о наборе дуг обратной связи может быть решена за полиномиальное время. Эти графы описывают поток управления в структурированных программах для многих языков программирования. Хотя структурированные программы часто порождают плоские направленные графы потока, определение редуцируемости не требует, чтобы граф был плоским. Если задача о минимальном наборе дуг обратной связи ограничена турнирами, то для нее существует полиномиальная схема аппроксимации, которая обобщается на взвешенную версию задачи. Также известен субекспоненциальный параметризованный алгоритм для взвешенных наборов дуг обратной связи на турнирах. Задача о максимальном ациклическом подграфе для плотных графов также имеет полиномиальную схему аппроксимации. Ее основные идеи заключаются в применении случайного округления к линейно-программированию, расслабляющему задачу, и в дерандомизации полученного алгоритма с использованием обходов на экспандерных графах.

NP-жесткость

Для того, чтобы применить теорию NP-полноты к задаче о минимальном наборе дуг обратной связи, необходимо преобразовать проблему из оптимизационной (какое минимальное количество ребер можно удалить, чтобы разрушить все циклы) в эквивалентную задачу принятия решения, с ответом «да» или «нет» (возможно ли удалить не более *k* ребер). Таким образом, задача принятия решения о наборе дуг обратной связи принимает на вход как ориентированный граф, так и число *k*. Она спрашивает, можно ли разрушить все циклы, удалив не более *k* ребер, или, эквивалентно, существует ли ациклический подграф, содержащий не менее *n-k* ребер. Эта задача является NP-полной, что означает, что ни она, ни исходная оптимизационная задача не имеют полиномиальных алгоритмов. Она входила в первоначальный набор из 21 NP-полных задач, предложенный Ричардом М. Карпом; NP-полнота этой задачи была доказана Карпом и Юджином Лоулером путем показа, что экземпляры другой сложной задачи – задачи о вершинном покрытии – могут быть сведены к эквивалентным экземплярам задачи принятия решения о наборе дуг обратной связи. Некоторые NP-полные задачи становятся проще при ограничении их входных данных специальными случаями. Однако для наиболее важного специального случая задачи о наборе дуг обратной связи, а именно случая турниров, задача остается NP-полной.

Недоступность

Класс сложности APX определяется как множество задач оптимизации, для которых существует алгоритм полиномиального времени приближения, достигающий постоянного коэффициента приближения. Хотя таких приближений для задачи о минимальном наборе обратных дуг неизвестно, эта задача является APX-трудной, что означает, что точные приближения для неё могли бы быть использованы для получения столь же точных приближений для всех остальных задач в APX. Как следствие доказательства трудности, если P ≠ NP, не существует алгоритма полиномиального времени приближения с коэффициентом лучше 1,3606. Это тот же порог трудности приближения, который известен для задачи о вершинном покрытии, и в доказательстве используется сведение Карпа — Лоулера из задачи о вершинном покрытии к задаче о минимальном наборе обратных дуг, которое сохраняет качество приближений. Другим сведением показано, что задача о максимальном ациклическом подграфе также является APX-трудной и NP-трудной для приближения с точностью до 65/66 от оптимального значения. Трудность приближения этих задач также изучалась при использовании непроверенных вычислительных предположений, стандартных в теории вычислительной сложности, но более сильных, чем P ≠ NP. Если верна гипотеза об уникальных играх, то задачу о минимальном наборе обратных дуг трудно приблизить в полиномиальное время с точностью до любого постоянного коэффициента, а задачу о максимальном наборе обратных дуг трудно приблизить с точностью до коэффициента , для . За пределами полиномиального времени для алгоритмов приближения, если верна гипотеза об экспоненциальном времени, то для каждого минимальный набор обратных дуг не имеет приближения с точностью до коэффициента , которое можно вычислить за субекспоненциальное время.

Теория

В плоских ориентированных графах задача о наборе дуг обратной связи подчиняется теореме "минимум-макс": минимальный размер набора дуг обратной связи равен максимальному числу реберно-непересекающихся ориентированных циклов, которые можно найти в графе. Это неверно для некоторых других графов; например, первая иллюстрация показывает ориентированную версию неплоского графа, в котором минимальный размер набора дуг обратной связи равен двум, а максимальное число реберно-непересекающихся ориентированных циклов — только одному. Каждый турнирный граф имеет гамильтонов путь, и гамильтоновым путям соответствует один к одному минимальные наборы дуг обратной связи, не пересекающиеся с соответствующим путем. Гамильтонов путь для набора дуг обратной связи находится путем обращения направления его дуг и нахождения топологического порядка полученного ациклического турнира. Каждая последовательная пара в этом порядке должна быть непересекающейся с наборами дуг обратной связи, иначе можно найти меньший набор дуг обратной связи, изменив направление этой пары. Таким образом, этот порядок задает путь по дугам исходного турнира, покрывающий все вершины. И наоборот, из любого гамильтонова пути множество ребер, соединяющих более поздние вершины пути с более ранними, образует набор дуг обратной связи. Он минимален, поскольку каждое его ребро принадлежит циклу с ребрами гамильтонова пути, который не пересекается с другими такими циклами. В турнире может случиться так, что минимальный набор дуг обратной связи и максимальный ациклический подграф близки к половине числа ребер. Более точно, каждый турнирный граф имеет набор дуг обратной связи размера , а некоторые турниры требуют размера . Для почти всех турниров размер составляет не менее . Любой ориентированный ациклический граф можно вложить в качестве подграфа большего турнирного графа таким образом, что является единственным минимальным набором дуг обратной связи турнира. Размер этого турнира определяется как "число обращения" , и среди ориентированных ациклических графов с одинаковым числом вершин он максимален, когда сам является (ациклическим) турниром. Ориентированный граф имеет эйлеров цикл, если он сильно связен и каждая вершина имеет одинаковое число входящих и исходящих ребер. Для такого графа с ребрами и вершинами размер минимального набора дуг обратной связи всегда не меньше . Существует бесконечно много эйлеровых ориентированных графов, для которых эта граница достигается. Если ориентированный граф имеет вершин, причем не более трех ребер на вершину, то у него есть набор дуг обратной связи, состоящий не более чем из ребер, и некоторые графы требуют такого количества. Если ориентированный граф имеет ребер, причем не более четырех ребер на вершину, то у него есть набор дуг обратной связи, состоящий не более чем из ребер, и некоторые графы требуют такого количества.

In planar directed graphs, the feedback arc set problem obeys a min max theorem: the minimum size of a feedback arc set equals the maximum number of edge disjoint directed cycles that can be found in the graph. This is not true for some other graphs; for instance the first illustration shows a directed version of the non planar graph in which the minimum size of a feedback arc set is two, while the maximum number of edge disjoint directed cycles is only one. Every tournament graph has a Hamiltonian path, and the Hamiltonian paths correspond one for one with minimal feedback arc sets, disjoint from the corresponding path. The Hamiltonian path for a feedback arc set is found by reversing its arcs and finding a topological order of the resulting acyclic tournament. Every consecutive pair of the order must be disjoint from the feedback arc sets, because otherwise one could find a smaller feedback arc set by reversing that pair. Therefore, this ordering gives a path through arcs of the original tournament, covering all vertices. Conversely, from any Hamiltonian path, the set of edges that connect later vertices in the path to earlier ones forms a feedback arc set. It is minimal, because each of its edges belongs to a cycle with the Hamiltonian path edges that is disjoint from all other such cycles. In a tournament, it may be the case that the minimum feedback arc set and maximum acyclic subgraph are both close to half the edges. More precisely, every tournament graph has a feedback arc set of size , and some tournaments require size For almost all tournaments, the size is at least Every directed acyclic graph can be embedded as a subgraph of a larger tournament graph, in such a way that is the unique minimum feedback arc set of the tournament. The size of this tournament has been defined as the "reversing number" of , and among directed acyclic graphs with the same number of vertices it is largest when is itself an (acyclic) tournament. A directed graph has an Euler tour whenever it is strongly connected and each vertex has equal numbers of incoming and outgoing edges. For such a graph, with edges and vertices, the size of a minimum feedback arc set is always at least There are infinitely many Eulerian directed graphs for which this bound is tight. If a directed graph has vertices, with at most three edges per vertex, then it has a feedback arc set of at most edges, and some graphs require this many. If a directed graph has edges, with at most four edges per vertex, then it has a feedback arc set of at most edges, and some graphs require this many.