Fast algorithm to find pair of triangles with a common edge in a complete graph

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!

2 Answers

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.

This is known as the 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.

• Aha!Thank you so much Daniel for the direction. – Zahra Dec 13 '19 at 20:03