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?

  • $\begingroup$ @moose: So you're asking for an maximum induced subgraph without directed triangle, right? $\endgroup$ Commented Mar 28, 2011 at 8:00
  • $\begingroup$ 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. $\endgroup$ Commented Mar 28, 2011 at 8:16
  • $\begingroup$ It should be easy to reduce the 3-hitting set problem, hence NP-hard. $\endgroup$ Commented Mar 28, 2011 at 9:21
  • $\begingroup$ @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. $\endgroup$ Commented Mar 28, 2011 at 9:54
  • 1
    $\begingroup$ I'd suggest changing the title to "Finding the largest subgraph without a directed triangle" or something like that. $\endgroup$
    – arnab
    Commented Mar 28, 2011 at 20:41

1 Answer 1


The problem of finding a maximum set with no induced directed triangles is NP-complete via a reduction from maximum independent set.

Let G=(V,E) be an undirected graph and k be an integer, for which we wish to know whether there is an independent set of at least k vertices. Let |V|=n. From G construct a directed graph G'=(V',A'), where V' consists of the disjoint union of V and n additional vertices. For each undirected edge in G create two directed edges between the same vertices in G'. In addition, connect each of the n additional vertices in G' by edges in both directions to the vertices in V, but do not add edges between any two of the n additional vertices.

Then, a triangle-free set of vertices in G' consists either of a subset of V only (with at most n vertices) or it contains some vertices in the set of additional vertices together with an independent set of vertices in G. Therefore, there exists a triangle-free set of size n+k in G' iff there exists an independent set of size k in G.

However, this reduction produces many 2-cycles, so it leaves open the possibility that the problem might be easier in the case that the input graph has no 2-cycles, which you say is the case for your inputs. Unfortunately this special case is still hard: a more complicated reduction based on the same idea shows that the problem remains NP-complete even for 2-cycle-free graphs. In the more complicated reduction, add mn additional vertices rather than simply n. Replace each undirected edge in G by a directed edge, oriented arbitrarily. For each directed edge uv connecting two vertices of V, make n additional vertices in V', each of them connected to u and v to form a directed triangle. Then the resulting graph has mn+k vertices in a triangle-free set iff the original graph has k vertices in an independent set.

  • $\begingroup$ Thanks David for your detailed answer. It will take some time for me to understand your post completely. May I contact you if I have some more questions to this topic? $\endgroup$ Commented Mar 30, 2011 at 21:31

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.