# Negative Triangle Detection (Graph Triangle Problems)

## 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

## 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))$
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))$
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)$
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))$
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))$
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))$
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))$
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)$
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

## 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}$
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$
Negative Triangle Search if: to-time: $T(n)$ where $T(n)/n$ is decreasing
then: from-time: $O(T(n))$
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}$
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$
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$
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
Minimum Witness Finding if: to-time: $T(n)$ where $n$ is the number of nodes in the graph
then: from-time: $O(T(n))$
All Pairs Minimum Witness (APMW) if: to-time: $T(n)$
then: from-time: $O(T(n^{1/3})n^{2})$
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)$