Графтардағы барлық циклдарды жоятын жиектер жиынтығы

Кіріспе

Граф теориясы мен графикалық алгоритмдерде, кері байланыс доғасы жиынтығы немесе кері байланыс жиегі жиынтығы — графтың жиектерінің ішкі жиыны, онда графтың әрбір циклында кем дегенде бір жиек болады. Осы жиектерді графтан жою барлық циклдарды бұзады, нәтижесінде берілген графтың ациклді субграфы пайда болады, ол көбінесе бағытталған ациклді граф деп аталады. Ең аз мүмкін жиектері бар кері байланыс доғасы жиынтығы — минималды кері байланыс доғасы жиынтығы, оны жою ең үлкен ациклді субграфты қалдырады; осы оптимизациялық мәселелердің салмақты түрлері де қолданылады. Егер кері байланыс доғасы жиынтығы минималды болса, яғни одан кез келген жиекті жою кері байланыс доғасы жиынтығы емес, кіші жиынды тудырса, онда оның қосымша қасиеті бар: оның барлық жиектерін жоюдың орнына, оларды кері бұру бағытталған ациклді графты тудырады. Кері байланыс доғасы жиынтықтары схемалық талдау, химиялық инженерия, тұйықталуды шешу, дәрежелі дауыс беру, спорттық жарыстарда бәсекелестерді бағалау, математикалық психология, этология және графты салу салаларында қолданылады. Минималды кері байланыс доғасын және максималды ациклді субграфты табу NP-қиын мәселе; оны экспоненциалды уақытта немесе белгілі бір параметрге қатысты шешімді табуға болатын уақытта шешуге болады. Полиномдық уақытта минималды кері байланыс доғасы жиынтығын полилогарифмдік жуықтау қатынасы шегінде және максималды ациклді субграфтарды тұрақты фактор шегінде жуықтауға болады. Екеуін де қандай да бір тұрақты фактордан жақын жуықтау қиын, бұл ерекше ойындар туралы болжаммен күшейтілуі мүмкін. Турнирлік графтар үшін минималды кері байланыс доғасын дәлірек жуықтауға болады, ал жазық графтар үшін екі мәселені де полиномдық уақытта дәл шешуге болады. Тығыз байланысты мәселе — кері байланыс төбесі жиынтығы, ол бағытталған немесе бағытталмаған графтың әрбір циклынан кем дегенде бір төбесін қамтитын төбелер жиынтығы. Бағытталмаған графтарда, жайылма ағаштар ең үлкен ациклді субграфтар болып табылады, ал жайылма ағашты құру кезінде жойылған жиектердің саны — циклдық рангі.

Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph. Feedback arc sets have applications in circuit analysis, chemical engineering, deadlock resolution, ranked voting, ranking competitors in sporting events, mathematical psychology, ethology, and graph drawing. Finding minimum feedback arc sets and maximum acyclic subgraphs is NP hard; it can be solved exactly in exponential time, or in fixed parameter tractable time. In polynomial time, the minimum feedback arc set can be approximated to within a polylogarithmic approximation ratio, and maximum acyclic subgraphs can be approximated to within a constant factor. Both are hard to approximate closer than some constant factor, an inapproximability result that can be strengthened under the unique games conjecture. For tournament graphs, the minimum feedback arc set can be approximated more accurately, and for planar graphs both problems can be solved exactly in polynomial time. A closely related problem, the feedback vertex set, is a set of vertices containing at least one vertex from every cycle in a directed or undirected graph. In undirected graphs, the spanning trees are the largest acyclic subgraphs, and the number of edges removed in forming a spanning tree is the circuit rank.

Қолданбалар

Турнирлік графиктегі кері байланыс доғасын табу арқылы реттеуге немесе тізімдеуге қатысты бірнеше мәселелерді шешуге болады, бұл әр төбе арасында бір қабырғасы бар бағытталған график. Кері байланыс доғасы жиынтығының қабырғаларын кері бұру, бірегей топологиялық ретілемесі қажетті тізімдеме ретінде қолданылатын бағытталған ациклдік графикті жасайды. Бұл әдістің қолданылуы мыналарды қамтиды: «Рунд-робин» жүйесі бар спорттық жарыстарда әр ойынның нәтижесі ойынның жеңілісінен жеңімпазына бағытталған қабырға арқылы тіркелуі мүмкін. Нәтижелік графиктегі ең аз кері байланыс доғасын табу, оның қабырғаларын кері бұру және топологиялық ретке келтіру барлық бәсекелестердің тізімдемесін жасайды. Тізімдеме таңдаудың барлық әртүрлі жолдарының арасында, бұл төменгі рейтингтегі бәсекелес жоғары рейтингтегі бәсекелесті жеңген ойындардың жалпы санын азайтады. Көптеген спорт түрлері топтық турнирлердегі рейтинг жүйелерінде әр ойын үшін берілген ұпайларға негізделген қарапайым әдістерді қолданады; бұл әдістер ең аз күйзеліс тізімдемесіне тұрақты жуықтама бере алады. Приматологияда және жалпы этологияда доминанттық иерархиялар көбінесе байқалған доминанттық мінез-құлықтағы ең аз кері бұрылыстар бар ретке келтіруді іздеу арқылы анықталады, бұл ең аз кері байланыс доғасы жиынтығының тағы бір түрі. Математикалық психологияда субъектілердің объектілер жиынтығының тізімдемесін белгілі бір критерийге сәйкес, мысалы, олардың қалауын немесе өлшемді қабылдауын анықтау қызығушылық тудырады, бұл барлық объектілер жұптарының арасындағы жұптық салыстыруларға негізделген. Турнирлік графиктегі ең аз кері байланыс доғасы мүмкіндігінше аз жұптық нәтижелермен келіспейтін тізімдеме береді. Егер осы салыстырулар әрбір жұптық ретке келтіру үшін тәуелсіз ықтималдықтарға әкелсе, онда жалпы тізімдеменің ең жоғары ықтималдық бағасын осы ықтималдықтарды логарифмдік ықтималдықтарға айналдырып, нәтижесінде турнирдегі ең төменгі салмақты кері байланыс доғасын табу арқылы алуға болады. Элементтерді сызықтық ретке келтірудің статистикалық және зерттеулік деректерді талдаудағы мәселесі, сериялау үшін бірдей ең жоғары ықтималдықпен тізімдеме қолданылуы мүмкін, егер элементтер арасындағы жұптық салыстыруды қамтамасыз ететін деректер болса. Реттелген дауыс беруде Кемень-Янг әдісін кандидаттардың жұптары бойынша сол жұп үшін қарама-қарсы тізімдемені қалайтындардың санын барынша азайтатын тізімдеме іздеу ретінде сипаттауға болады. Бұл ең төменгі салмақты кері байланыс доғасы ретінде құрастырылып, шешілуі мүмкін, мұнда төбелер кандидаттарды білдіреді, қабырғалар әр бас-бас бәсекеде жеңімпазды бейнелеуге бағытталған, ал әр қабырғаның құны бас-бас жеңіліске жоғары тізімдеме беру арқылы бақытсыз боларлық сайлаушылардың санын білдіреді. Кері байланыс доғаларының тағы бір ерте қолданылуы жүйелі логикалық схемаларды жобалауға қатысты, онда сигналдар әрқашан кіріс пен шығыстан үнемі өркендеудің орнына схема арқылы циклдарда таралуы мүмкін. Мұндай схемаларда ең аз кері байланыс доғасы сигналды ақпарат жоғалмай таратуға мүмкіндік беру үшін күшейткіш қажетті нүктелердің санын сипаттайды. Асинхронды компоненттерден жасалған синхронды схемаларда синхрондылыққа кері байланыс доғасының қабырғаларына сағатталған қақпаларды орналастыру арқылы қол жеткізуге болады. Сонымен қатар, кері байланыс доғасы жиынтығында схеманы кесу қалған схеманы комбинациялық логикаға дейін азайтады, оның талдауын жеңілдетеді, ал кері байланыс доғасы жиынтығының мөлшері кесу арқылы схеманың мінез-құлқын түсіну үшін қанша қосымша талдау қажет екенін анықтайды. Сол сияқты, химиялық инженериядағы процестердің ағынын есептеуде кері байланыс доғасы жиынтығында процестердің ағыны диаграммасының қабырғаларын бұзу және осы қабырғалардағы мәндер үшін барлық мүмкіндіктерді болжау немесе сынап көру процестің қалған бөлігін жүйелі түрде талдауға мүмкіндік береді. Бұл қолданбада қабырғаларды осылай бұзу идеясы «жару» деп аталады. Қабатталған графиктік сызбада берілген бағытталған графиктің төбелері реттелген кіші жиынтықтарға (сызбаның қабаттарына) бөлінеді және әр кіші жиынтық осы сызбаның көлденең сызығы бойымен орналастырылады, ал қабырғалар осы қабаттар арасында жоғары және төмен қарай созылады. Бұл суретте жоғары және төменгі қабырғаларды араластырмау үшін, қабырғалардың көпшілігі немесе барлығы төмен қарай бағытталған болуы қажет, соның арқасында суреттегі қолжетімділік қатынастары көрінеуірек болады. Бұл ең аз немесе минималды кері байланыс доғасын табу арқылы, осы жиынтықтағы қабырғаларды кері бұру арқылы және содан кейін қабаттарға бөлуді нәтижелік ациклдік графиктің топологиялық ретімен сәйкес келетіндей етіп таңдау арқылы қол жеткізіледі. Кері байланыс доғалары қабатталған графиктік сызбаның басқа бір кіші мәселесі үшін де қолданылған, яғни қалапты қабаттардың ішіндегі төбелердің ретін анықтау үшін. Операциялық жүйелердегі тұйыққа түсуді шешуде, тұйыққа түсуді бұзу үшін ең аз тәуелділіктерді жою мәселесі ең аз кері байланыс доғасын табудың бірі ретінде модельделуі мүмкін. Алайда, осы жиынтықты табудың есептеу қиындығы және операциялық жүйе компоненттерінде жылдамдық қажеттілігіне байланысты, осы қолданбада нақты алгоритмдердің орнына эвристикалар көбінесе қолданылады.

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.

Дұрыс

Минималды кері байланыс доғасының жиынтығын табудың бір жолы – төбелердің ретін іздеу, яғни реттелгендегі кейінгі төбелерден алдыңғы төбелерге бағытталған жиектердің санын мүмкіндігінше азайту. Төбесі бар графтың барлық мүмкін орналасуларын іздеу уақыт алады, бірақ Held–Karp алгоритміне негізделген динамикалық бағдарламалау әдісі оңтайлы орналасуды уақыт ішінде таба алады, сонымен қатар экспоненциалды көлемдегі жадты пайдаланады. Төбелерді екі тең ішкі жиынға бөлуді және әрбір ішкі жиын ішінде рекурсияны қолдануды тексертін бөліп-жеңу алгоритмі, полиномдық жадты пайдалана отырып, мәселені уақыт ішінде шеше алады. Параметрленген күрделілікте алгоритмдердің уақыты кіріс графтың мөлшерімен ғана емес, сонымен қатар графтың жеке параметрімен де өлшенеді. Атап айтқанда, минималды кері байланыс доғасы жиынтығы мәселесі үшін, табиғи параметр деп аталатын – минималды кері байланыс доғасы жиынтығының мөлшері. Төбесі бар графтарда, табиғи параметрмен , кері байланыс доғасы жиынтығы мәселесін, оны эквивалентті кері байланыс төбесі жиынтығы мәселесіне түрлендіру және параметрленген кері байланыс төбесі жиынтығы алгоритмін қолдану арқылы уақыт ішінде шешуге болады. Бұл алгоритмдегі экспонента тұрақты, параметріне тәуелсіз болғандықтан, бұл алгоритм тұрақты параметрлік деп аталады. Табиғи параметрден басқа да параметрлер зерттелді. Динамикалық бағдарламалауды пайдаланатын тұрақты параметрлік алгоритм уақыт ішінде минималды кері байланыс доғасы жиынтығын таба алады, мұнда – негізгі бағытталмаған графтың тізбектік рангі. Тізбектік ранг – кері байланыс доғасы жиынтығының бағытталмаған аналогы, графты жайылмалы ағашқа дейін азайту үшін графтан алып тастау керек жиектердің ең аз саны; оны минималды кері байланыс доғасы жиынтығынан есептеу әлдеқайда оңай. Ағаш ені бар графтар үшін, графтың ағашқа жіктелуі бойынша динамикалық бағдарламалау графтың мөлшеріне полиномдық және экспоненциалды уақыт гипотезасына сәйкес уақыт ішінде минималды кері байланыс доғасын таба алады. Кері байланыс доғасы жиынтығының мөлшерін азайтудың орнына, зерттеушілер кез келген төбеден алынған жиектердің максималды санын азайтуға да қарады. Мәселенің бұл түрін сызықтық уақыт ішінде шешуге болады. Барлық минималды кері байланыс доғасы жиынтықтарын жиынтық бойынша полиномдық кешігумен алгоритммен тізімдеуге болады.

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 толықтығының теориясын ең аз кері байланыс доғасы жиынтығына қолдану үшін, мәселені оңтайландыру мәселесінен (барлық циклдарды бұзу үшін қанша қабырғаны жою қажет) теңшестірілген шешім нұсқасына өзгерту керек, жауабы «иә» немесе «жоқ» болатын (қабырғаларды жою мүмкін бе?). Осылайша, кері байланыс доғасы жиынтығының шешім нұсқасы кіріс ретінде бағытталған графты және санды қабылдайды. Ол барлық циклдарды ең көп дегенде белгілі бір сан қабырғаны жою арқылы бұзуға бола ма, немесе балама ретінде, кем дегенде белгілі бір саны бар ациклді кішкентай граф бар ма деп сұрайды. Бұл мәселе NP толық, яғни оның өзі де, оңтайландыру мәселесі де полиномиалдық уақыт алгоритмдеріне ие болмайды деп күтілуде. Бұл Ричард М. Карптың бастапқы 21 NP толық проблемасының бірі болды; оның NP толықтығы Карп пен Юджин Лоулердің басқа бір қиын мәселе – төбелік жабын (vertex cover) мәселесінің кірістерін кері байланыс доғасы жиынтығының шешім мәселесіне баламалы кірістерге түрлендіруге болатынын көрсету арқылы дәлелденді. Кейбір NP толық мәселелер кірістері арнайы жағдайлармен шектелгенде оңайырақ болуы мүмкін. Бірақ кері байланыс доғасы жиынтығының ең маңызды арнайы жағдайы – турнирлер жағдайында мәселе NP толық болып қалады.

Қатынасу мүмкін еместігі

APX күрделілік класы тұрақты жуықтау қатынасына қол жеткізетін полиномиалдық уақыттық жуықтау алгоритмі бар оптимизациялық мәселелерден тұратын ретінде анықталады. Мұндай жуықтаулар кері байланыс доғалары жиыны мәселесі үшін белгілі болмаса да, бұл мәселе APX қиын екені мәлім, яғни оның дәл жуықтамалары APX-тегі басқа барлық мәселелер үшін ұқсас дәл жуықтамалар алуға пайдаланылуы мүмкін. Қиындық дәлелінің салдарынан, егер P = NP болмаса, оның полиномиалдық уақыттық жуықтау қатынасы 1.3606-дан жоғары емес. Бұл төбелік жамылғы үшін белгілі жуықтау қиындығының шегімен бірдей, ал дәлелдемеде төбелік жамылғыдан кері байланыс доғалары жиынына дейінгі Карп-Лоулер азайтуы қолданылады, ол жуықтамалардың сапасын сақтайды. Басқа азайту арқылы, максималды ациклдік кішграф мәселесі де APX қиын, ал оптималды 65/66 үлесіне дейін NP қиын жуықталады. Бұл мәселелердің жуықтау қиындығы есептеу күрделілігі теориясында стандартты, бірақ 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.