<p>There's a straightforward algorithm.  For each edge <span class="math-container">$(u,v)$</span>, compute the multiset of products of weights of paths of length 2 from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>:</p>

<p><span class="math-container">$$S_{u,v} = \{\text{wt}(u,t) \cdot \text{wt}(t,w) : (u,t) \in E \land (t,w) \in E\}.$$</span></p>

<p>These multisets can be computed in at most <span class="math-container">$O(|V| \cdot |E|)$</span> time.  In practice it suffices to enumerate all edges <span class="math-container">$(u,v)$</span>, then enumerate all edges <span class="math-container">$(u,t)$</span> incident on <span class="math-container">$u$</span>, then check whether <span class="math-container">$(t,w)$</span> is an edge.</p>

<p>Next, for each edge <span class="math-container">$(u,v)$</span> and each pair of values <span class="math-container">$x,x' \in S_{u,v}$</span>, plot the point <span class="math-container">$(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$</span> on the scatterplot.  This can be done in at most <span class="math-container">$O(|V|^2 \cdot |E|)$</span> time.</p>

<p>It might not be easy to do asymptotically significantly better than this.  For a complete graph, the scatter plot can have <span class="math-container">$\Theta(|V|^4)$</span> points, so there is no hope for an algorithm whose running time is faster than <span class="math-container">$O(|V|^4)$</span> on complete graphs; and this algorithm takes <span class="math-container">$O(|V|^4)$</span> time on complete graphs, so it is asymptotically optimal for such graphs.  For sparse graphs, this algorithm takes <span class="math-container">$O(|V|^3)$</span> time, and there might be some hope to get the running time a little faster for sparse graphs.</p>

<p>If it's still too slow, rather than creating the entire scatterplot, you could sample the points on the scatterplot and plot that.  One way to do that is to compute the multisets <span class="math-container">$S_{u,v}$</span>, then for each edge <span class="math-container">$(u,v)$</span> sample a bunch of pairs of values <span class="math-container">$x,x' \in S_{u,v}$</span> and plot the points <span class="math-container">$(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$</span> on the scatterplot for each such pair.  If there are a lot of points on the scatterplot, plotting a random sample of the points should also be sufficient for visualization purposes and should give you a good sense of the "shape" of the scatterplot.</p>

CC BY-SA 4.0
2019-12-13T20:29:37.577Z
2019-12-13T20:29:37.577Z
D.W.
<p>This is known as the <a href="https://en.m.wikipedia.org/wiki/Subgraph_isomorphism_problem" rel="nofollow noreferrer">subgraph isomorphism problem</a> where you search for the 4 vertex graph with 5 edges (i.e. two triangles sharing an edge).
This problem is known to be NP hard but should be feasible for your case. However I am not an expert on this field. 
Many graph libraries have implemented the VF2 algorithm.</p>

CC BY-SA 4.0
2019-12-13T20:03:48.987Z
Aha!Thank you so much Daniel for the direction.
Zahra M
CC BY-SA 4.0
2019-12-13T19:58:59.907Z
2019-12-13T19:58:59.907Z
Daniel
<p>Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value <span class="math-container">$energy$</span> that is the multiplication of its edge weights. The question is to first find pair of triangles that have a common edge, and then draw the energy-energy scatter plot for these pairs.</p>

<p>For example, take this adjacency matrix:
<span class="math-container">$$ \begin{bmatrix} 0 &amp; 1 &amp; 2 &amp; 3 \\ 1 &amp; 0 &amp; 4 &amp; 5 \\ 2 &amp; 4 &amp; 0 &amp; 6 \\ 3 &amp; 5 &amp; 6 &amp; 0 \\\end{bmatrix}$$</span>
For this graph we have 6 pair of triangles with a common edge: </p>

<p><span class="math-container">$1: (1,2,3) \space with \space (1,2,4) $</span>, (with <span class="math-container">$(1-2)$</span> as the common edge)</p>

<p><span class="math-container">$2: (1,2,3) \space with \space (1,3,4) $</span>, (with <span class="math-container">$(1-3)$</span> as the common edge)</p>

<p><span class="math-container">$3: (1,2,4) \space with \space (1,3,4) $</span>, (with <span class="math-container">$(1-4)$</span> as the common edge)</p>

<p><span class="math-container">$4: (1,2,3) \space with \space (2,3,4) $</span>, (with <span class="math-container">$(2-3)$</span> as the common edge)</p>

<p><span class="math-container">$5: (1,3,4) \space with \space (2,3,4) $</span>, (with <span class="math-container">$(2-4)$</span> as the common edge)</p>

<p><span class="math-container">$6: (1,2,4) \space with \space (2,4,3) $</span>, (with <span class="math-container">$(3-4)$</span> as the common edge)</p>

<p>Now it's quite easy to draw the energy-energy plot for these pairs. For each pair from 1 to 6, on the x axes we take the energy value of the first triangle in the pair, and on the y axes we put the energy value of the second triangle in the pair. So we will have a plot with 6 points, for each point <span class="math-container">$ (x,y) $</span>,  <span class="math-container">$x $</span> is the energy value of the first triangle in the pair, and <span class="math-container">$y$</span> is the energy value of the second triangle in the pair.</p>

<p>I'm fine with solving this problem when the number of nodes is quite small. But I need to run this algorithm on a graph with 116 nodes. So I need to find an efficient algorithm. I'm using MatLab and I appreciate any optimize algorithm for this problem. </p>

<p>Thank you so much!</p>

<graph-algorithms><complexity>
Fast algorithm to find pair of triangles with a common edge in a complete graph
Zahra M
# Fast algorithm to find pair of triangles with a common edge in a complete graph

(Asked by: username_0 on 2019-12-13)

Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles that have a common edge, and then draw the energy-energy scatter plot for these pairs.

For example, take this adjacency matrix:
$$ \begin{bmatrix} 0 & 1 & 2 & 3 \\ 1 & 0 & 4 & 5 \\ 2 & 4 & 0 & 6 \\ 3 & 5 & 6 & 0 \\\end{bmatrix}$$
For this graph we have 6 pair of triangles with a common edge:

$1: (1,2,3) \space with \space (1,2,4) $, (with $(1-2)$ as the common edge)

$2: (1,2,3) \space with \space (1,3,4) $, (with $(1-3)$ as the common edge)

$3: (1,2,4) \space with \space (1,3,4) $, (with $(1-4)$ as the common edge)

$4: (1,2,3) \space with \space (2,3,4) $, (with $(2-3)$ as the common edge)

$5: (1,3,4) \space with \space (2,3,4) $, (with $(2-4)$ as the common edge)

$6: (1,2,4) \space with \space (2,4,3) $, (with $(3-4)$ as the common edge)

Now it's quite easy to draw the energy-energy plot for these pairs. For each pair from 1 to 6, on the x axes we take the energy value of the first triangle in the pair, and on the y axes we put the energy value of the second triangle in the pair. So we will have a plot with 6 points, for each point $ (x,y) $, $x $ is the energy value of the first triangle in the pair, and $y$ is the energy value of the second triangle in the pair.

I'm fine with solving this problem when the number of nodes is quite small. But I need to run this algorithm on a graph with 116 nodes. So I need to find an efficient algorithm. I'm using MatLab and I appreciate any optimize algorithm for this problem.

Thank you so much!

**Tags:** graph-algorithms, complexity

---

## 2 answers

### Answer by username_1 on 2019-12-13. Score: 1 | Accepted answer

There's a straightforward algorithm. For each edge $(u,v)$, compute the multiset of products of weights of paths of length 2 from $u$ to $v$:

$$S\_{u,v} = \{\text{wt}(u,t) \cdot \text{wt}(t,w) : (u,t) \in E \land (t,w) \in E\}.$$

These multisets can be computed in at most $O(|V| \cdot |E|)$ time. In practice it suffices to enumerate all edges $(u,v)$, then enumerate all edges $(u,t)$ incident on $u$, then check whether $(t,w)$ is an edge.

Next, for each edge $(u,v)$ and each pair of values $x,x' \in S\_{u,v}$, plot the point $(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$ on the scatterplot. This can be done in at most $O(|V|^2 \cdot |E|)$ time.

It might not be easy to do asymptotically significantly better than this. For a complete graph, the scatter plot can have $\Theta(|V|^4)$ points, so there is no hope for an algorithm whose running time is faster than $O(|V|^4)$ on complete graphs; and this algorithm takes $O(|V|^4)$ time on complete graphs, so it is asymptotically optimal for such graphs. For sparse graphs, this algorithm takes $O(|V|^3)$ time, and there might be some hope to get the running time a little faster for sparse graphs.

If it's still too slow, rather than creating the entire scatterplot, you could sample the points on the scatterplot and plot that. One way to do that is to compute the multisets $S\_{u,v}$, then for each edge $(u,v)$ sample a bunch of pairs of values $x,x' \in S\_{u,v}$ and plot the points $(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$ on the scatterplot for each such pair. If there are a lot of points on the scatterplot, plotting a random sample of the points should also be sufficient for visualization purposes and should give you a good sense of the "shape" of the scatterplot.


---

### Answer by username_2 on 2019-12-13. Score: 0

This is known as the [subgraph isomorphism problem](https://en.m.wikipedia.org/wiki/Subgraph_isomorphism_problem) where you search for the 4 vertex graph with 5 edges (i.e. two triangles sharing an edge).
This problem is known to be NP hard but should be feasible for your case. However I am not an expert on this field.
Many graph libraries have implemented the VF2 algorithm.

> **Comments:**
> **username_0**: Aha!Thank you so much Daniel for the direction.  

---

