3 articles
Acyclic orientation
An acyclic orientation of a graph is an assignment of a direction to each edge with no directed cycle, making the result a DAG; counting them is #P-complete.
Feedback arc set
A feedback arc set of a directed graph is a set of arcs whose removal makes the graph acyclic; finding a smallest one is NP-hard.
Feedback vertex set
A feedback vertex set, also known as a cycle cutset, is a set of vertices whose removal leaves a graph acyclic; finding the smallest one is an NP-complete problem.