Negative Triangle Detection

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 nodes

$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