Triangle Collection* (Graph Triangle Problems)

Description

See Definition 3 of reference.

Related Problems

Generalizations: Triangle Detection

Related: Negative Triangle Detection, Negative Triangle Search, Negative Triangle Listing, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph

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
dynamic 4/3-Diameter	assume: SETH or {3}SUM Hypothesis or APSP Hypothesis then: there exists no incremental (or decremental) algorithm that approximates the diameter of unweighted graph within a factor of ${4}/{3}-\epsilon$ running in amortized time $O(n^{1/{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$. Furthermore, if we allow node insertions in the incremental case the bound is $O(n^{0.{618}-\epsilon'})$	2016	https://arxiv.org/abs/1602.06705	link
dynamic 4/3-Diameter	assume: SETH or {3}SUM Hypothesis or APSP Hypothesis then: there exists no static ${4}/{3}-\epsilon$ approximation to the diameter on unweighted graphs running in $O((n\sqrt{m})^{1-\epsilon'})$ time for any $\epsilon,\epsilon' > {0}$ and an number of edges $m$	2016	https://arxiv.org/abs/1602.06705	link
dynamic 4/3-Diameter	assume: SETH or {3}SUM Hypothesis or APSP Hypothesis then: there exists no static ${4}/{3}-\epsilon$ approximation with additive error $O(m^\delta)$ with running time $O(m^{\frac{3}{2}({1}-\delta)-\epsilon'})$ or incremental/decremental algorithm with amortized time $O(m^{\frac{1}{2}-\frac{3\delta}{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$	2016	https://arxiv.org/abs/1602.06705	link