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

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-30T21:31:57.413Z
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?
Martin Thoma
CC BY-SA 2.5
2011-03-28T18:40:05.470Z
2011-03-28T20:55:45.947Z
2011-03-28T20:55:45.947Z
David Eppstein
<p>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.</p>

<p>Do you know an algorithm for that?</p>

CC BY-SA 2.5
2011-03-28T08:00:10.357Z
@moose: So you're asking for an maximum induced subgraph without directed triangle, right?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-28T08:16:39.117Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-28T09:21:47.457Z
It should be easy to reduce the 3-hitting set problem, hence NP-hard.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-28T09:54:11.703Z
@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.
Martin Thoma
CC BY-SA 2.5
2011-03-28T20:41:24.473Z
I'd suggest changing the title to "Finding the largest subgraph without a directed triangle" or something like that.
arnab
CC BY-SA 2.5
2011-03-28T21:44:57.517Z
@arnab: I changed it. Thanks for the suggestion.
Martin Thoma
CC BY-SA 3.0
2013-11-02T05:05:11.423Z
NP-hardness follows by [Lewis and Yannakakis](http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/hered.pdf)
Austin Buchanan
<ds.algorithms><graph-algorithms>
Algorithm for finding the largest subgraph without a directed triangle
Martin Thoma
# Algorithm for finding the largest subgraph without a directed triangle

(Asked by: username_0 on 2011-03-28)

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?

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: @moose: So you're asking for an maximum induced subgraph without directed triangle, right?  
> **username_1**: 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.  
> **username_2**: It should be easy to reduce the 3-hitting set problem, hence NP-hard.  
> **username_0**: @username_1: 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.  
> **username_3**: I'd suggest changing the title to "Finding the largest subgraph without a directed triangle" or something like that.  
> **username_0**: @username_3: I changed it. Thanks for the suggestion.  
> **username_4**: NP-hardness follows by [Lewis and Yannakakis](http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/hered.pdf)  

---

## 1 answers

### Answer by username_5 on 2011-03-28. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  

---

