2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is "local transitivity" the same as a triangle? Or could it (for instance) involve more than 3 vertices? $\endgroup$ – D.W. Sep 4 at 19:59
  • $\begingroup$ 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), then remove any of the three vertices of the $bcd$ triangle. Are there some constraints missing? (e.g., remove the minimal number of vertices such that no triangles remain?) Or, if not, can you correct the example? $\endgroup$ – D.W. Sep 4 at 23:54
  • $\begingroup$ 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?" $\endgroup$ – D.W. Sep 4 at 23:55
  • $\begingroup$ @D.W. Thank you, nice questions, I updated my post. $\endgroup$ – Ignat Insarov Sep 5 at 10:49
  • $\begingroup$ Ahh, sorry, my fault: I missed that this is a directed graph. Thanks for the clarifications! We generally prefer that you ask only one question per post; if you have multiple questions, they can be asked separately. $\endgroup$ – D.W. Sep 5 at 15:21
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Must I understand that, while triangle enumeration is a well-worn path, cutting them away — not so much? $\endgroup$ – Ignat Insarov Sep 5 at 19:22
  • $\begingroup$ @IgnatInsarov, I don't know whether your removal problem has been studied before or not. Sorry. My knowledge is limited. $\endgroup$ – D.W. Sep 5 at 19:25
  • $\begingroup$ This is not at all what I meant. What I mean is that, given that you possess in your knowledge some random sample of works in this area, from your emphasis on triangle counting a probabilistic argument can be derived. $\endgroup$ – Ignat Insarov Sep 5 at 19:35
  • $\begingroup$ @IgnatInsarov, I'm not an expert on algorithms and I don't specialize in that area; it's just something I enjoy learning about for fun on the side. So, don't read too much into my ignorance. $\endgroup$ – D.W. Sep 5 at 20:16

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.