Algorithm for finding the largest subgraph without a directed triangle

I would like to find the largest set of vertices in a directed graph. This set should not contain a cycle with exactly three vertices. Cycles with less vertices aren't possible with the given graphs; larger cycles can be in the set.

Do you know an algorithm for that?

• @moose: So you're asking for an maximum induced subgraph without directed triangle, right? Commented Mar 28, 2011 at 8:00
• If so, this is likely to be NP-hard, while I haven't found such a reference. Maybe it can be derived from some known NP-hard results of detecting induced subgraphs, since most of them are pretty hard. Commented Mar 28, 2011 at 8:16
• It should be easy to reduce the 3-hitting set problem, hence NP-hard. Commented Mar 28, 2011 at 9:21
• @Hsien-Chih Chang 張顯之: Exactly. Could you please suggest some knowen NP-hard results of detecting induced subgraphs? If you post it as an answer, I'll accept it if nobody else gives me a better answer until Wednesday. Commented Mar 28, 2011 at 9:54
• I'd suggest changing the title to "Finding the largest subgraph without a directed triangle" or something like that. Commented Mar 28, 2011 at 20:41