Editing Directed acyclic graph (section)

== Computational problems ==
=== Topological sorting and recognition ===
{{Main|Topological sorting}}
[[Topological sorting]] is the algorithmic problem of finding a topological ordering of a given DAG. It can be solved in [[linear time]].<ref name="clrs">{{Introduction to Algorithms|edition=2|mode=cs2}}  Section 22.4, Topological sort, pp. 549–552.</ref> Kahn's algorithm for topological sorting builds the vertex ordering directly. It maintains a list of vertices that have no incoming edges from other vertices that have not already been included in the partially constructed topological ordering; initially this list consists of the vertices with no incoming edges at all. Then, it repeatedly adds one vertex from this list to the end of the partially constructed topological ordering, and checks whether its neighbors should be added to the list. The algorithm terminates when all vertices have been processed in this way.<ref name="j50" /> Alternatively, a topological ordering may be constructed by reversing a [[postorder]] numbering of a [[depth-first search]] graph traversal.<ref name="clrs" />

It is also possible to check whether a given directed graph is a DAG in linear time, either by attempting to find a topological ordering and then testing for each edge whether the resulting ordering is valid<ref>For [[depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> or alternatively, for some topological sorting algorithms, by verifying that the algorithm successfully orders all the vertices without meeting an error condition.<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>

=== Construction from cyclic graphs ===
Any undirected graph may be made into a DAG by choosing a [[total order]] for its vertices and directing every edge from the earlier endpoint in the order to the later endpoint. The resulting [[Orientation (graph theory)|orientation]] of the edges is called an [[acyclic orientation]]. Different total orders may lead to the same acyclic orientation, so an {{mvar|n}}-vertex graph can have fewer than {{math|''n''!}} acyclic orientations. The number of acyclic orientations is equal to {{math|{{!}}''χ''(−1){{!}}}}, where {{mvar|χ}} is the [[chromatic polynomial]] of the given graph.<ref>{{citation|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref>

[[File:Graph Condensation.svg|thumb|upright=1.5|The yellow directed acyclic graph is the [[Condensation (graph theory)|condensation]] of the blue directed graph. It is formed by [[Edge contraction|contracting]] each [[strongly connected component]] of the blue graph into a single yellow vertex.]]
Any directed graph may be made into a DAG by removing a [[feedback vertex set]] or a [[feedback arc set]], a set of vertices or edges (respectively) that touches all cycles. However, the smallest such set is [[NP-hard]] to find.<ref>{{Garey-Johnson}}, Problems GT7 and GT8, pp.&nbsp;191–192.</ref> An arbitrary directed graph may also be transformed into a DAG, called its [[condensation (graph theory)|condensation]], by [[Edge contraction|contracting]] each of its [[strongly connected component]]s into a single supervertex.<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> When the graph is already acyclic, its smallest feedback vertex sets and feedback arc sets are [[empty set|empty]], and its condensation is the graph itself.

=== Transitive closure and transitive reduction ===
The transitive closure of a given DAG, with {{mvar|n}} vertices and {{mvar|m}} edges, may be constructed in time {{math|''O''(''mn'')}} by using either [[breadth-first search]] or [[depth-first search]] to test reachability from each vertex.<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref> Alternatively, it can be solved in time {{math|''O''(''n''<sup>''ω''</sup>)}} where {{math|''ω''&nbsp;<&nbsp;2.373}} is the [[Computational complexity of matrix multiplication#Matrix multiplication exponent|exponent for matrix multiplication algorithms]]; this is a theoretical improvement over the {{math|''O''(''mn'')}} bound for [[dense graph]]s.<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref>

In all of these transitive closure algorithms, it is possible to distinguish pairs of vertices that are reachable by at least one path of length two or more from pairs that can only be connected by a length-one path. The transitive reduction consists of the edges that form length-one paths that are the only paths connecting their endpoints. Therefore, the transitive reduction can be constructed in the same asymptotic time bounds as the transitive closure.<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref>

=== Closure problem ===
{{Main|Closure problem}}
The [[closure problem]] takes as input a vertex-weighted directed acyclic graph and seeks the minimum (or maximum) weight of a closure – a set of vertices ''C'', such that no edges leave ''C''. The problem may be formulated for directed graphs without the assumption of acyclicity, but with no greater generality, because in this case it is equivalent to the same problem on the condensation of the graph. It may be solved in polynomial time using a reduction to the [[maximum flow problem]].<ref>{{citation
 | last = Picard | first = Jean-Claude
 | doi = 10.1287/mnsc.22.11.1268
 | issue = 11
 | journal = [[Management Science (journal)|Management Science]]
 | mr = 0403596
 | pages = 1268–1272
 | title = Maximal closure of a graph and applications to combinatorial problems
 | volume = 22
 | year = 1976}}.</ref>

=== Path algorithms ===
Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find [[shortest path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|processing the vertices in a topological order]], and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref>