Negative Triangle Detection (Graph Triangle Problems)
Jump to navigation
Jump to search
Description
Given an $n$ node graph $G = (V, E)$ with edge weights $w: E \rightarrow W$, determine whether there is a negative triangle, i.e. three vertices that form a triangle with total edge weights summing to a negative number.
Related Problems
Generalizations: Triangle Detection
Subproblem: Negative Triangle Search
Related: Negative Triangle Listing, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph, Triangle Collection*
Parameters
n: number of vertices
m: number of edges
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions TO Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Matrix Product Verification | if: to-time: $T(n)$ then: from-time: $O(T({2}n))$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.1 | link |
| Metricity | if: to-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$, and $T(n,M)$ is nondecreasing then: from-time: $O(n^{2}) + T(O(n), O(M))$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.2 | link |
| Shortest Cycle | if: to-time: $T(n,M)$ where there are $n$ nodes and weights in $({1}, M)$ then: from-time: $T(n, O(M))$ where there are $n$ nodes and weights in $(-M, M)$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.3 | link |
| Maximum Subarray | 2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.4 | link | |
| Betweenness Centrality (BC) | if: to-time: $\tilde{O}(T(n,m))$ for $n$-node $m$-edge graph then: from-time: $\tilde{O}T(n,m))$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 2.2 | link |
| Radius | if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$ then: from-time: $\tilde{O}(T(n,m,M))$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 2.3 | link |
| Median | if: to-time: $\tilde{O}(T(n,M))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$ then: from-time: $\tilde{O}T(n,M))$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 2.4 | link |
| All-Nodes Median Parity | if: to-time: $\tilde{O}(T(n,M))$ for $n$-node $m$-edge graph with integer weights in $(-M, M)$ then: from-time: $\tilde{O}T(n,M))$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 2.5 | link |
| All-Nodes Positive Betweenness Centrality | if: to-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$ then: from-time: $\tilde{O}(T(n,m,M))$ for $n$-node $m$-edge graph with integer weights in $(-M,M)$ |
2015 | https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Lemma 4.4 | link |
| 2D Maximum Subarray | if: to-time: $O(n^{3-\epsilon})$ on $n\times n$ matrices then: from-time: $O(n^{3-\epsilon})$ on $n$ vertex graphs |
2016 | https://arxiv.org/pdf/1602.05837.pdf | link |
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Directed, Weighted APSP | if: to-time: $n^{3-\epsilon}$ for some $\epsilon >{0}$ then: from-time: $n^{3-\epsilon'}$ for some $\epsilon' > {0}$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893 | link |
| Matrix Product | if: to-time: $T(n)$ where $T(n)/n$ is decreasing then: from-time: $O(n^{2} \cdot T(n^{1/3})\log W)$ for two $n\times n$ matrices where $W$ is the maxint of $R$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.2 | link |
| Negative Triangle Search | if: to-time: $T(n)$ where $T(n)/n$ is decreasing then: from-time: $O(T(n))$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.1 | link |
| Negative Triangle Listing | if: to-time: $O(n^{3-\epsilon}\log^c M)$ for some $\epsilon > {0}$ and where $M$ is the maxint of $R$ then: from-time: $O(n^{3-\epsilon'}\log^c M)$ for some $\epsilon' > {0}$ for listing $\Delta = O(n^{3-\delta})$ negative triangles with fixed $\delta > {0}$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.3 | link |
| Matrix Product | if: to-time: $O(n^{3}/\log^c n)$ for some constant $c$ then: from-time: $O((\log W) n^{3} / \log^c n)$ where $W$ is maxint of $R$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Corollary 4.1 | link |
| Matrix Product | if: to-time: $T(n)$ then: from-time: $O(mp\cdot T(n^{1/3}) \log W)$ s.t. $mp \leq n^{3}$ and $\sqrt{p} \leq m \leq p^{2}$ and multiplying two matrices of dimensions $m \times n$ and $n \times p$ over $R$ and $W$ is the maxint of $R$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.4 | link |
| Matrix Product | if: to-time: $T(n)$ where $T(n)/n^{2}$ is decreasing then: from-time: $O(n^{2} \cdot T(n^{1/3})\log n)$ for two $n\times n$ matrices with high probability |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.5 | link |
| Minimum Witness Finding | if: to-time: $T(n)$ where $n$ is the number of nodes in the graph then: from-time: $O(T(n))$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.4 | link |
| All Pairs Minimum Witness (APMW) | if: to-time: $T(n)$ then: from-time: $O(T(n^{1/3})n^{2})$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.5 | link |
| Metricity | if: to-time: $O(n^{2}) + T(O(n), O(M))$ where $T(n,M)$ is nondecreasing then: from-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$ |
2018 | https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.2 | link |
| Maximum Subarray | 1998 | https://dl.acm.org/doi/abs/10.5555/314613.314823 | link |