 Important polynomial time computational problems on DAGs include topological sorting ( finding a topological ordering ) , construction of the transitive closure and transitive reduction ( the largest and smallest DAGs with the same reachability relation , respectively ) , and the closure problem , in which the goal is to find a minimum @-@ weight subset of vertices with no edges connecting them to the rest of the graph . <unk> a directed graph with cycles into a DAG by <unk> as few vertices or edges as possible ( the feedback vertex set and feedback edge set problem , respectively ) is NP @-@ hard , but any directed graph can be made into a DAG ( its condensation ) by contracting each strongly connected component into a single <unk> . The problems of finding shortest paths and longest paths can be solved on DAGs in linear time , in contrast to arbitrary graphs for which shortest path algorithms are slower and longest path problems are NP @-@ hard . 
