3
$\begingroup$

I am interested in two problems, which seem to be related, solving each will advance me in other possible directions.

In both problems, $G=(V,E)$ is a positively-weighted undirected graph. Denote its weight function by $w$.

Having $w$, a weight-distance between $2$ vertices is the smallest sum of weights on a path between these vertices. The edge-distance is simply the number of edges between them, on a path that will ignore the weight function and will only count the number of edges.

The first problem: For any $v\in V$, find the weight-distance to all $u\in V$ such that there exists a vertex $z\in V$ for which: $(v,z)(z,u)\in E$. Basically, its like All-Pairs Shortest Path, just for pairs of vertices within edge-distance exactly $2$. Only these pairs are of interest to me, and I would like the algorithm to be as nearly to quadratic time as possible (Say, $|V|^{\frac{5}{2}}$ is already inefficient for me).

My attempt was a sort of Dijkstra combined with a BFS (or the first two levels of a BFS tree), but this leads to $|E|$ time, which makes it $|V||E|$, which is way inefficient for me.

The second problem might be even harder. Consider $G$. The weight of a triangle is simply the sum of its' edges' weights. I want to find for each vertex its minimal weight triangle. As I am not attempting to enumerate all triangles, I do believe this can be solved faster than $|E|^{\frac{3}{2}}$ for triangle enumeration.

For this problem, I have considered attempting a degeneracy-based approach, by trying to sort edges and disqualifying edges that are "too heavy" - but this never gave fruit to an actual algorithm. The total runtime here should also likely be $|V|^2$ or very near, $|V|^{\frac{5}{2}}$ is too heavy.

I suspect the second problem I presented might be even harder then the first, therefore I am not aware if such algorithms can be made, or if it would apply certain other problems are too easy from what they are believed to be.

A general note is that the graph might be dense, so $|V||E|$ is too much time for either one.

Additionally, I would like to avoid matrix multiplication algorithms, yet if the runtime (without MM) is an expected runtime, that is acceptable, as I believe having a deterministic algorithm without MM might be too hard. So a random algorithm (without MM) with an expected runtime of as near $|V|^2$ as possible is also efficient.

Improve this question
$\endgroup$
4
  • $\begingroup$ Note that if you take any positively weighted graph $G$, add a new special vertex $x$, and then add edges $e_u := \{u, x\}$ for every $u \in V(G)$, with weight $w(e_u) = +\infty$ each (e.g., $+\infty := \max_{e \in E(G)} w(e)$), then all pairs of nodes have length $2$ paths, so your problem becomes general APSP. The modified graph has only one extra vertex and a linear number of extra edges, so a $|V|^2$ algorithm for your problem would imply a $|V|^2$ algorithm for APSP. $\endgroup$
    – Bernardo Subercaseaux
    Commented May 16 at 16:28
  • $\begingroup$ If you are not attempting to enumerate all triangles in the second problem, then you can introduce a new graph $H=G_1$x$G_2$x$G_3$x$G_4$, where $G_k=(V,E_k=\{\})$ is a null graph, for each edge $e_{ij}\in E$ introduce a directed edge between vertex $i\in G_k$ and vertex $j\in G_{k+1}$. Note that, you can introduce $V_1=V_4=\{v\}$ and $V_2=V_3=N_v$. Now, in H, shortest path between each vertex v in $G_1$ and the same vertex v in $G_4$ is similar to a minimum triangle on vertex v in G. $\endgroup$
    – Majid Zohrehbandian
    Commented May 19 at 18:40
  • $\begingroup$ @MajidZohrehbandian Wouldn't that simply be $|V||E|$? $\endgroup$
    – Mařík Savenko
    Commented May 20 at 16:01
  • $\begingroup$ @BernardoSubercaseaux That's a good insight. What if I will consider all $u,v$ such that the path $P:u---> v$ with the smallest weight-edge has $2$ edges in it. I will look to find only these $u,v$. I think it'll relax the problem a bit. $\endgroup$
    – Mařík Savenko
    Commented May 20 at 16:03

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you very much! However, I forgot to mention I was looking for random without MM. My bad. (That's why I thought some randomness might assist). Alas, the algorithm doesn't have to be exactly quadratic, but even near $|V|^2$ is good. $\endgroup$
    – Mařík Savenko
    Commented May 12 at 12:21
  • $\begingroup$ There are randomized algorithms for APSP as well; see if you can draw some inspiration from that. $\endgroup$
    – codeR
    Commented May 13 at 7:11
  • $\begingroup$ I have added a possible practical approach, please see if that helps. $\endgroup$
    – codeR
    Commented May 19 at 7:34
  • $\begingroup$ @Thanks. I am still not sure the runtime is as you describe. Wouldn't copying the distances, even for 1-edge-distance, be $O(\deg v)$? Therefore, $|E|$ for every edge, totaling in $|E|\cdot |V|$? Because at each edge, you copy the distances. Though my main issue is that the average degree might be $O(n)$... $\endgroup$
    – Mařík Savenko
    Commented May 20 at 16:00
  • $\begingroup$ Recall that $\sum deg(v) = 2 \times |E|$, assuming $deg(v) = O(n)$ might be an overkill. My basic intuition is that if your input graph is sparse, then you can have a low-complexity exact algorithm. You can also look into sparse matrix multiplication algorithms as well. $\endgroup$
    – codeR
    Commented May 23 at 7:39

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.