Skip to main content
Computer Science

Return to Answer

update
Source Link
codeR
codeR
  • 2k
  • 6
  • 16

Your first problem basically boils down to a transitive closure in a graph. Here, matrix multiplication can be used. The best-known algorithm to date has a complexity of $n^{2.371552}$. In my opinion, finding a quadratic algorithm for this problem is as hard as finding the same for the matrix multiplication problem.

Once you have the 2-edge-distance all-pair-shortest-path matrix, you can combine (add and take min) that with the weighted adjacency matrix to solve the triangle problem. The time complexity of just this step will be $O(n^2)$. The first step remains the dominant one.

UPDATE
Taking inspiration from how network routing tables are updated (a distributed APSP approach), here is an approach for the first problem. For each vertex $v$, we maintain an $O(n)$ storage. Now for each vertex $v$, inform all of its neighbors of its presence, and thus we have all $1$-edge-distances with us. This takes a total of $O(|V| + |E|)$ time, which is at most $O(n^2)$. Now each vertex broadcasts its $1$-edge-distance table to all of its neighbours. Thus, at each vertex, we get atmost $n$ such tables. These tables can now be merged to compute the required $2$-edge-distance paths. The expected running time of this step is $O(n \times \tilde{d^2})$, where $\tilde{d}$ is the average degree of the graph, which is typically small compared to $n$ in practical graphs.

Your first problem basically boils down to a transitive closure in a graph. Here, matrix multiplication can be used. The best-known algorithm to date has a complexity of $n^{2.371552}$. In my opinion, finding a quadratic algorithm for this problem is as hard as finding the same for the matrix multiplication problem.

Once you have the 2-edge-distance all-pair-shortest-path matrix, you can combine (add and take min) that with the weighted adjacency matrix to solve the triangle problem. The time complexity of just this step will be $O(n^2)$. The first step remains the dominant one.

Your first problem basically boils down to a transitive closure in a graph. Here, matrix multiplication can be used. The best-known algorithm to date has a complexity of $n^{2.371552}$. In my opinion, finding a quadratic algorithm for this problem is as hard as finding the same for the matrix multiplication problem.

Once you have the 2-edge-distance all-pair-shortest-path matrix, you can combine (add and take min) that with the weighted adjacency matrix to solve the triangle problem. The time complexity of just this step will be $O(n^2)$. The first step remains the dominant one.

UPDATE
Taking inspiration from how network routing tables are updated (a distributed APSP approach), here is an approach for the first problem. For each vertex $v$, we maintain an $O(n)$ storage. Now for each vertex $v$, inform all of its neighbors of its presence, and thus we have all $1$-edge-distances with us. This takes a total of $O(|V| + |E|)$ time, which is at most $O(n^2)$. Now each vertex broadcasts its $1$-edge-distance table to all of its neighbours. Thus, at each vertex, we get atmost $n$ such tables. These tables can now be merged to compute the required $2$-edge-distance paths. The expected running time of this step is $O(n \times \tilde{d^2})$, where $\tilde{d}$ is the average degree of the graph, which is typically small compared to $n$ in practical graphs.

Source Link
codeR
codeR
  • 2k
  • 6
  • 16

Your first problem basically boils down to a transitive closure in a graph. Here, matrix multiplication can be used. The best-known algorithm to date has a complexity of $n^{2.371552}$. In my opinion, finding a quadratic algorithm for this problem is as hard as finding the same for the matrix multiplication problem.

Once you have the 2-edge-distance all-pair-shortest-path matrix, you can combine (add and take min) that with the weighted adjacency matrix to solve the triangle problem. The time complexity of just this step will be $O(n^2)$. The first step remains the dominant one.