It is well known that the problem of finding a maximal acyclic subgraph of a digraph is NP-complete.


Is this the case also when the digraph is symmetric ,i.e. if $(a,b)$ is a link, then $(b,a)$ is also a link?



Maximal acyclic subgraph
Arbitrarily label the vertices $1,\ldots,n$. Choose all edges $a\to b$ such that $b\gt a$. This is acyclic and exactly half the directed edges in the graph, which is obviously the best possible.


If the edges are weighted then it is again NP-complete, since the weights of $a\to b$ and $b\to a$ can be chosen with sufficient disparity to mimic the standard digraph case.


