Like transitive reduction, but removing vertices rather than edges?

Question

Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in E$ — that is to say, the relation restricted to $x, y, z$ is transitive, there is a triangle. Let us call this situation a "local transitivity". My goal is to obtain all the subgraphs of $G$ induced by cutting middle vertices from local transitivities until none remain, which I dub "resolution".

There may be multiple solutions. For instance, consider a graph given by this relation:

  a b c d  
a □ ■ ■ □  
b □ □ ■ ■  
c □ □ □ ■  
d □ □ □ □  

(It looks like a square with one diagonal.)

There are two ways it can be resolved:

  a b d        a c d  
a □ ■ □      a □ ■ □  
b □ □ ■      c □ □ ■  
d □ □ □      d □ □ □  

One way I can compute the resolutions of a graph is by giving a "non-deterministic" function $f :G \rightarrow \{G\}$ that removes any single local transitivity. Repeatedly applying $f$ to any graph, I will eventually converge to a set of induced subgraphs completely devoid of local transitivities.

One way to define $f$ is by considering all the triples of distinct vertices and checking them for local transitivity. From each matching triple, the middle vertex is extracted, and any of these vertices is cut. But there is about $|V|^3$ such triples.

Is there a better way? Is there prior art that I may study?

 

P.S. Answering to questions from the comments:

1. Is "local transitivity" the same as a triangle? Or could it (for instance) involve more than 3 vertices?

   In the case I have in mind, it is specifically triangles that I need to remove. But I can see how a generalization may be offered where, given two paths $p_1, p_2: a \dots b$ such that $|p_1| \leq n$ and $|p_2| \leq m$ (counting edges), we can remove the longer. My specific problem is then the special case with $n = 1, m = 2$.

2. In your example, I think there are more than two ways it can be resolved. For example, you could remove vertex a (from the abc triangle) ...

   I was thinking that it is only allowed to remove a midpoint from a triangle, so that "initial" and "terminal" vertices cannot be removed, and therefore the length of the shortest path is preserved.

3. What's your question? Is your question "can I enumerate all triangles faster than $O(|V|^3)$ time?" Is your question "how efficiently can I find all possible triangle-free subgraphs?"

   This and that too. Primarily, I need the triangle-free induced subgraphs. Enumerating triangles is only a means to this end, but it may be a useful technique for other algorithms, elsewhere, so would be good to know.

Answer 1

There's a $O(n^\omega)$-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex. Here $O(n^\omega)$ is the running time for matrix multiplication. See, e.g., Number of triangles in an undirected graph, Is it a valid graph canonical form?, https://cstheory.stackexchange.com/q/9972/5038. This may or may not be faster in practice.

To enumerate a list of all such triangles can take $\Theta(n^3)$ time in the worst case, for instance, in the case where you have a complete graph on $n$ vertices, as then you have $\Theta(n^3)$ triangles in the graph, so just outputting them takes $\Theta(n^3)$ time.