Timeline for The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 16 at 8:08 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jun 18 at 8:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| S May 23 at 17:07 | history | bounty ended | CommunityBot | ||
| S May 23 at 17:07 | history | notice removed | CommunityBot | ||
| May 20 at 16:03 | comment | added | Mařík Savenko | @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. | |
| May 20 at 16:01 | comment | added | Mařík Savenko | @MajidZohrehbandian Wouldn't that simply be $|V||E|$? | |
| May 19 at 18:40 | comment | added | Majid Zohrehbandian | 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. | |
| May 16 at 16:28 | comment | added | Bernardo Subercaseaux | 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. | |
| S May 15 at 15:34 | history | bounty started | Mařík Savenko | ||
| S May 15 at 15:34 | history | notice added | Mařík Savenko | Canonical answer required | |
| May 12 at 12:20 | history | edited | Mařík Savenko | CC BY-SA 4.0 |
added 97 characters in body
|
| May 11 at 11:43 | answer | added | codeR | timeline score: 0 | |
| May 10 at 12:46 | history | edited | Mařík Savenko | CC BY-SA 4.0 |
added 95 characters in body
|
| May 10 at 11:48 | history | edited | Mařík Savenko | CC BY-SA 4.0 |
added 275 characters in body
|
| May 9 at 20:27 | history | asked | Mařík Savenko | CC BY-SA 4.0 |