4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – Chao Xu
    Jun 10, 2013 at 20:31

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – user742
    Jun 23, 2013 at 10:09
  • $\begingroup$ 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. $\endgroup$
    – Chao Xu
    Jun 23, 2013 at 11:02
  • $\begingroup$ 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. $\endgroup$
    – user742
    Jun 23, 2013 at 13:01
  • $\begingroup$ 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. $\endgroup$
    – Chao Xu
    Jun 23, 2013 at 18:29
  • $\begingroup$ 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. $\endgroup$
    – user742
    Jun 23, 2013 at 19:09
2
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • $\begingroup$ By the problem definition is clear that we can suppose $M\in O(n)$. $\endgroup$
    – user742
    Jun 23, 2013 at 10:15
  • $\begingroup$ @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. $\endgroup$
    – András Salamon
    Jun 23, 2013 at 13:39
  • $\begingroup$ 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. $\endgroup$
    – user742
    Jun 23, 2013 at 14:22
  • $\begingroup$ P.S: In the case OP looks for algorithm for $n\in o(M)$ your suggestion is good. $\endgroup$
    – user742
    Jun 23, 2013 at 19:14

Your Answer

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

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