# An efficient way to find a pair of unrelated edges

I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph.

Given a dense an undirected graph $$G=(V,E)$$ where I have a large amount of vertices and $$|E|\in O(|V|^2)$$ many edges, I would like to check whether it contains a cross/parallel (unrelated) edge pair. These are $$2$$ edges $$\left(v_1, v_2\right)$$ and $$\left(v_3, v_4\right)$$ such that for any $$i (excluding $$i=1,j=2$$ and $$i=3,j=4$$) there is no edge $$\left( v_i , v_j \right)$$. In other words, the only $$2$$ edges are $$\left(v_1, v_2\right)$$ and $$\left(v_3, v_4\right)$$.

This is a subroutine that is expected to be called frequently (on different graphs, so I can't use partial results from previous iterations), so I'm trying to save valuable runtime.

The initial naive approach is $$|E|^2 = |V|^4$$ by having's $$O(1)$$ boolean conditions to be checked for any pair of edges, but this is highly not effective.

I have been thinking to look at $$\overline{G}$$, and check to see if it is a chordal graph and also if it contains $$C_4$$. I know that a LEX-BFS approach can verify in $$O(|V|+|E|)$$ if $$\overline{G}$$ is chordal or not (see Rose, Lueker & Tarjan (1976)), and that in $$O(|V|^2)$$ it is possible to check if $$\overline{G}$$ contains $$C_4$$ by a variant of BFS.

However, I am not sure if this approach if there is a more efficient approach. It seems that too much time is "wasted" upon checking if $$C_4$$ exists, and that's why I'm looking for an alternative way.

Clarifications:

• I'm looking for a subset of $$4$$ vertices $$\left\{ v_1 ,\ldots , v_4 \right\}$$ such that $$\left(v_1,v_2\right),\left(v_3,v_4\right) \in E$$ and these are the only edges induces by these vertices.
• In other words, for any other $$i,j$$ there is no edge $$\left(v_i , v_j \right)\notin E$$.
• My usecase for this graph is dense, so may assume $$|E| \in O(|V|^2)$$.
• The graph itself is persumed to have many vertices, so I'm trying to reduce the runtime somewhere to linear or $$|V| \log |V|$$ or $$|V|^2$$ but $$|V|^3$$ can take too much considering the amount of vertices I have (Because this is a subroutine that would be invoked many times).
• I am not sure if your solution is correct. Suppose the graph $\bar{G}$ is not chordal. Then, you are checking if there is exits a $C_4$ in the graph. By that, I am assuming that you are checking if there exists a cycle on $4$ vertices; however that cycle might contains a chord. Note that there might exist another cycle of length say $5$ that does not contain any chord; thus keeping the graph $\bar{G}$ non-chordal. Commented Oct 31, 2023 at 18:27

This 2015 paper by Williams et al. considers induced subgraphs and shows how to find $$C_4$$ and co-$$C_4$$ in a graph $$G$$ time $$O(\min\{n^\omega, m^{\frac{4\omega-1}{2\omega+1}}\})$$, where $$n$$, $$m$$ are the number of vertices and edges of $$G$$, respectively, and $$\omega$$ is the matrix-multiplication exponent.
Since $$\omega < 2.372$$, this is a subcubic algorithm.