Assertion: directed graph | /r/HasProperty | made into dag
Facets:
value: by removing a feedback vertex
type: MANNER
value: by contracting each strongly connected component
type: MANNER
Source sentences:
text: Transforming a directed graph with cycles into a DAG by deleting as few vertices or edges as possible (the feedback vertex set and feedback edge set problem, respectively) is an NP-hard problem, but any directed graph can be made into a DAG (its condensation) by contracting each strongly connected component into a single supervertex.
text: 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.