2
$\begingroup$

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<j$ (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).
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Oct 31, 2023 at 18:27

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! I'll try implementing $\endgroup$ Commented Nov 9, 2023 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.