4
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Excellent! What if each link has a weight and I want to find the acyclic subgraph with maximal total weight? $\endgroup$
    – Ralph Lorentzen
    Commented May 16, 2016 at 13:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .