Clever Geek Handbook
📜 ⬆️ ⬇️

Cycle Cutting Rib Set

This directed graph has no cycles - it is impossible to come to any vertex back to the same point along arcs in the directions indicated by arrows.

In graph theory, a directed graph may contain oriented cycles , a ring of arcs having one direction. In some applications such cycles are undesirable, we can exclude them and get a directed acyclic graph (Directed Acyclic Graph, DAG). One way to exclude arcs is simply to remove arcs from the graph. Feedback Arc Set ( FAS ) or a loop - cutting set of edges is a set of arcs that, when removed from the graph, form a DAG. Looking at it from a different angle, this is a set containing at least one edge from each cycle of the graph.

A closely related concept is a , which includes at least one vertex from each cycle of a directed graph, and a minimal spanning tree , which is an undirected version of the problem of finding a cycle-cutting set of arcs.

The minimal set of arcs cutting cycles (which cannot be reduced in size by removing edges) has the additional property that if the edges in it are replaced by inverse ones and not deleted, the graph remains acyclic. Finding a small set of edges with this property is a key step in the [1] [2] .

Sometimes it is desirable to discard as few arcs as possible, forming the smallest cutting cycle set of arcs , or the dual largest acyclic subgraph . The task is a complex computational task for which some approximating solutions have been developed.

Content

  • 1 Example
  • 2 Smallest cutting loop set of arcs
    • 2.1 Theoretical Results
    • 2.2 Approximations
  • 3 notes
  • 4 Literature

Example

As a simple example, imagine the following hypothetical situation in which to get something you need to do something:

  • Your goal is to get a lawn mower.
  • Harry says he will give a lawn mower, but only in exchange for a microwave.
  • Jane says she will give the microwave, but only in exchange for the piano.
  • George says he will give the piano, but only in exchange for a lawn mower.

We can express this situation as a task on a graph. Let each vertex represent an object, and we add an arc from A to B, if we must have A to get B. Unfortunately, you do not have any of these three things, and since the graph is cyclic, you cannot do any of the things receive.

However, suppose you give George $ 100 for his piano. If he receives them, it will remove the arc from the lawnmower to the piano. Thus, the cycle is broken and you can make two exchanges to get the desired lawn mower. This single arc makes up a cycle-cutting set of arcs.

Smallest loop-cutting set of arcs

As in the example above, usually a price is associated with breaking the arc. For this reason, it is desirable to remove as few arcs as possible. Removing one arc is sufficient to break a simple cycle, but in the general case, determining the smallest number of arcs to delete is an NP-hard task, and it is called the smallest cycle-cutting set of arcs or the largest acyclic subgraph.

Theoretical Results

This problem, in particular, is difficult for edge k- connected graphs for large k , where each arc appears in many different cycles. The problem in the solvability variant, which is NP-complete , asks if all cycles can be cut by removing at most k arcs. This problem is included in the list of 21 NP-complete Karp problems [3] [4] .

Being NP-complete, the problem of finding a cycle-cutting set of arcs is - there is an algorithm for solving it, the operation time of which depends polynomially on the size of the input graph (but not depending on the number of edges), but the time exponentially depends on the number of edges in a cycle-cutting set of arcs [5] .

Viggo Kann showed in 1992 that the problem of finding the minimum cycle-cutting set of arcs is APX-complicated , which means that there exists a constant c such that, under the assumption P ≠ NP, there is no time-polynomial approximation algorithm , which always finds the set of edges, is a maximum c times greater than the optimal one [6] [7] . By 2006, the highest value of c , for which it is known that there is no such algorithm, is c = 1.3606 [8] . The best known approximation algorithm has the estimate O (log n log log n ) [7] [9] . For the dual problem of approximate calculation of the number of edges in an acyclic subgraph, an algorithm is possible with a coefficient slightly better 1/2 [10] [11] .

If the input digraphs are limited to tournaments , the task is known as the minimum feedback arc set problem on tournaments (the task of finding a loop-cutting set of arcs in tournaments , FAST). This limited problem allows an approximate scheme of polynomial time, and this statement remains true for a limited weighted version of the problem [12] . An algorithm with a fixed sub-exponential parameter for weighted FAST was proposed by Karpinsky and Shudi [13] .

On the other hand, if the edges are not oriented , the task of removing edges to reach the graph without cycles is equivalent to finding the minimum spanning tree , which can be easily done in polynomial time.

Zoom

Some approximation algorithms were developed for the problem [14] . A very simple algorithm is as follows:

  • We fix a random permutation of the vertices, i.e., we number them from 1 to n .
  • We construct two subgraphs, L and R , containing edges ( u , v ) , and for the first graph, u < v , for the second, u > v .

Now, both L and R are acyclic subgraphs of the graph G , and at least one of these graphs is no more than half the maximum acyclic subgraph [15] .

Notes

  1. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 265-302.
  2. ↑ Bastert, Matuszewski, 2001 , p. 87-120.
  3. ↑ Karp, 1972 , p. 85-103.
  4. ↑ Garey, Johnson, 1979 , p. 198.
  5. ↑ Chen, Liu, Lu, O'Sullivan, Razgon, 2008 .
  6. ↑ Kann, 1992 .
  7. ↑ 1 2 Crescenzi, Kann, Halldórsson, Karpinski, Woeginger, 2000 .
  8. ↑ Irit, Safra, 2005 , p. 439–485.
  9. ↑ Even, Naor, Schieber, Sudan, 1998 , p. 151–174.
  10. ↑ Berger, Shor, 1990 , p. 236-243.
  11. ↑ Eades, Lin, Smyth, 1993 , p. 319–323.
  12. ↑ Kenyon-Mathieu, Schudy, 2007 , p. 95-103.
  13. ↑ Karpinski, Schudy, 2010 , p. 3-14.
  14. ↑ Hassin, Rubinstein, 1994 , p. 133-140.
  15. ↑ Skiena, 2010 , p. 348; 559-561.

Literature

  • Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. - Prentice Hall , 1998 .-- S. 265-302. - ISBN 9780133016154 .
  • Oliver Bastert, Christian Matuszewski. Drawing Graphs: Methods and Models / Michael Kaufmann, Dorothea Wagner. - Springer-Verlag, 2001. - T. 2025. - S. 87–120. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 3-540-44969-8_5 .
  • Richard M. Karp. Complexity of Computer Computations. - New York: Plenum ,, 1972. - S. 85-103. - (Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, NY).
  • Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . - WH Freeman, 1979. - ISBN 0-7167-1045-5 .
  • Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem // Journal of the ACM . - 2008. - T. 55 , no. 5 . - DOI : 10.1145 / 1411509.1411511 .
  • Viggo Kann. On the Approximability of NP-complete Optimization Problems. - Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992.
  • Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard J. Woeginger. A compendium of NP optimization problems. - 2000.
  • Dinur Irit, Shmuel Safra. On the hardness of approximating minimum vertex cover // Annals of Mathematics . - 2005. - T. 162 , no. 1 . - S. 439–485 . - DOI : 10.4007 / annals.2005.162.439 .
  • G. Even, J. Naor, B. Schieber, M. Sudan. Approximating minimum feedback sets and multicuts in directed graphs // Algorithmica . - 1998. - T. 20 , no. 2 . - S. 151–174 . - DOI : 10.1007 / PL00009191 .
  • B. Berger, P. Shor. Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (SODA'90). - 1990. - S. 236–243.
  • P. Eades, X. Lin, WF Smyth. A fast and e ff ective heuristic for the feedback arc set problem // Information Processing Letters. - 1993 .-- T. 47 . - S. 319–323 . - DOI : 10.1016 / 0020-0190 (93) 90079-O .
  • Claire Kenyon-Mathieu, Warren Schudy. Proc. 39th ACM Symposium on Theory of Computing (STOC '07). - 2007. - S. 95–103. - DOI : 10.1145 / 1250790.1250806 .
  • M. Karpinski, W. Schudy. Proc. 21st ISAAC (2010). - 2010. - T. 6506. - S. 3-14. - ( Lecture Notes in Computer Science ). - DOI : 10.1007 / 978-3-642-17517-6_3 .
  • Refael Hassin, Shlomi Rubinstein. Approximations for the maximum acyclic subgraph problem // Information Processing Letters. - 1994.- T. 51 , no. 3 . - S. 133-140 . - DOI : 10.1016 / 0020-0190 (94) 00086-7 .
  • Steven Skiena. The Algorithm Design Manual. - 2nd. - Springer Science + Business Media , 2010 .-- ISBN 1-849-96720-2 .
Source - https://ru.wikipedia.org/w/index.php?title= Cutting_cycles_set_of_ribs&oldid = 93329955


More articles:

  • Eastlake Smith Gladys
  • Portrait of Charles I on the hunt
  • Yarder, Erica
  • Fokino (Kaluga Region)
  • Wilkins, William (politician)
  • Masks (album)
  • Clopiraralid
  • Diallo, Ibrahim
  • Cesar, Adolf
  • Berezhnaya, Tatyana Nikolaevna

All articles

Clever Geek | 2019