patternMinor
Efficiently checking if two star graphs are disjoint
Viewed 0 times
efficientlystararecheckinggraphstwodisjoint
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#12603, answer score: 3
Revisions (0)
No revisions yet.