Negative Triangle Listing (Graph Triangle Problems)

Description

Given an $n$ node graph $G = (V, E)$ with edge weights $w: E \rightarrow W$, list the negative triangles, i.e. three vertices that form a triangle with total edge weights summing to a negative number.

Related Problems

Generalizations: Negative Triangle Search

Related: Negative Triangle Detection, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph, Triangle Detection, 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
Negative Triangle Detection	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