1
$\begingroup$

If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic graph?

To be clear, the result is neither necessarily a tree (could have more than one way from A to B), nor is the graph still connected, could have disconnected components. I just can't have cycles.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

This is a classic NP-complete problem called Feedback Arc Set.

The problem is solvable in fixed parameter tractable time $k^{O(k)}$, and there is an approximation algorithm, however it's open whether there is a constant factor approximation.

The word feedback refers to a cycle in a graph, and the problem is "hitting" all cycles with as few arcs (directed edges) as possible.

Note that deleting an arc is equivalent to reversing it(!)

In so-called tournament graphs (compete digraphs), the problem is slightly easier. In undirected graphs, the problem is MST.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.