# Efficiently checking if two star graphs are disjoint

I have given an undirected graph $G$ with vertex $\{1, ... n\}$ and two star subgraphs $S_1$ and $S_2$, always consisting of ALL neighbors of a given vertex, and the goal is to check wether the two star graphs have a vertex in common. This will be will be executed $M$ times for $M$ a large integer.

My approach would be to store the graph in adjacency list format and for each vertex store its adjacency list in sorted order.

We can then check in $O(M n \log n)$ time in total if two star graphs of the sequence of $M$ star graph pairs have a vertex in common.

But maybe this can be done more efficiently?

• Is the question the same as the input is 2 vertices... and you answer the query does the two vertices have a common neighbor(the vertex itself is also considered as neighborhood) – Chao Xu Jun 10 '13 at 20:31

I assume the graph $G$ is fixed, and you are doing $M$ queries on $G$.

Your algorithm takes $O(Mn\log n+t)$ time, where $t$ is the amount of time to build the adjacency list. We can use the same time, but remove the log factor by merging the neighbor of $S_1$ and $S_2$ list in $O(n)$ time.

If $M \in \Omega(n)$, you can just compute the result for all queries in $O(n^2)$ time. Store the result in a new matrix $N$, initially all $0$s. Set $N_{i,j}=1$ for all $\{i,j\}\in \{i|M_{k,i}=1\}$. Thus $N_{i,j}=1$ iff $i$ and $j$ share a neighbor.

If you query for star $S_i,S_j$, it returns $\max(N_{i,j},M_{i,j})$, if it's $0$, then there is no common vertex for the stars.

It takes $O(M+n^2)$ time and $O(n^2)$ memory.

• This approach is $O(M\cdot n+n^2)$ not $O(M\cdot n)$, means when $M\in o(n)$, this is absolutely slower than adjacency list. – user742 Jun 23 '13 at 10:09
• You can build an adjacency matrix in $O(m)$ time if you have a minimum perfect hash. but sure even if it's the adjacency list version, one can do it in $O(Mn+t)$ time by merging the 2 neighbors, where $t$ is the time to build the adjacency list representation. – Chao Xu Jun 23 '13 at 11:02
• I cannot see what kind of magic is possible to do with hash. Anyway, I said your running time is wrong. If you edit it, still is really not a good answer and OP's way is much more better, and this answer motivate him/her to the wrong direction. – user742 Jun 23 '13 at 13:01
• I don't see why OP's algorithm is $O(Mn\log n)$ unless the graph is already given in the adjacency list form. Building an adjacency list can take $O(n^2)$ time too. – Chao Xu Jun 23 '13 at 18:29
• I did not said that OP's algorithm is in $O(M\cdot n\log n)$, I said that if $M\in o(n)$, your algorithm is absolutely slower than OP's algorithm. – user742 Jun 23 '13 at 19:09

As Chao Xu suggests, first create the adjacency matrix $A$. However, I would then compute the matrix $N=A+A^2$ in $O(n^{2.8})$ steps by using Strassen's matrix multiplication algorithm (or in time $O(n^3)$ using nothing fancy). Now $N_{uv} = 0$ iff the stars $S_u$ and $S_v$ do not intersect. This has a high setup cost, but can then support any number of queries of the form you want by a single lookup in the matrix.

To say more, one needs further information about the parameters: is $M$ larger than $n^2$, or is it between $n$ and $n^2$, or is it smaller than $n$; and what is the cost of doing a matrix lookup in your model of computation?

• By the problem definition is clear that we can suppose $M\in O(n)$. – user742 Jun 23 '13 at 10:15
• @Saeed Amiri: that is not clear to me at all, sorry. In many database applications, one may want to allow an identical query to be run on a fixed structure. Do you have some special insight into the OP's motivation? I think the question is quite underspecified and can be interpreted in different ways; I don't think it is up to those answering to try to second-guess what the OP intended. – András Salamon Jun 23 '13 at 13:39
• Actually I think there is no need to the second-guess, it's clear for me that if $M>n$ then there is no need to do anything special, except saving all possible queries in one matrix (like your way, ...). IMO the problem is when the $M\in o(n)$, Actually is it possible to find better than the adjacency list? or we can prove is impossible. At least for me this was the main concern when I read the question. – user742 Jun 23 '13 at 14:22
• P.S: In the case OP looks for algorithm for $n\in o(M)$ your suggestion is good. – user742 Jun 23 '13 at 19:14