I have an arbitrary directed, non-complete graph. I would like to find a maximal subset of nodes within that graph such that the induced subgraph has no cycles. I'm sure there must be a name for this problem in the literature - do you know what it is?

  • $\begingroup$ Thanks! Do you know how I can mark the question as answered, given that you answered in a comment? $\endgroup$ – lightning Dec 2 '18 at 3:51
  • $\begingroup$ I just transferred my comment to answer. So I will delete that comment. $\endgroup$ – Michael Dec 2 '18 at 4:55

This is the "maximum acyclic subgraph" problem (just search Google).

I once used such a thing for an info-theory bound on an "index coding" problem (but for a directed graph in that case), Lemma 1 here:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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