Triangle Detection (Graph Triangle Problems)

Description

Determine whether or not there is a triangle in a given graph

Related Problems

Subproblem: Negative Triangle Detection, Nondecreasing Triangle, Minimum Triangle, Triangle in Unweighted Graph, Triangle Collection*

Related: Negative Triangle Search, 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
Independent Set Queries	if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$ then: from-time: $O(n^{3} / \log^{c+1} n)$	2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 6.5	link
Dynamic st-Reach	assume: SETH then: for any fixed constants $\epsilon > {0}$, $c_1,c_2 \in ({0},{1})$, on graphs with $n$ nodes $|S|=\tilde{\Theta}(n^{c_1})$, $|T|=\tilde{\Theta(n^{c_2})}$, $m=O(n)$ edges, and capacaties in $\{1,\cdots,n\}$, target cannot be solved in $O((|S|T|m)^{1-\epsilon})$	2014	https://ieeexplore.ieee.org/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg	link
Strong Connectivity (dynamic)	let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$ if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$ then: Strong Triangle is false	2014	https://ieeexplore.ieee.org/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg	link
Dynamic Bipartite Maximum-Weight Matching	let $\gamma = (w-{1})/(w+{1}) \in ({1}/{3},{0.408})$ if: to-time: $O(m^{2\gamma-\epsilon})$ update and query times even after O(m^{1+\gamma-\epsilon}) preprocessing time for any $\epsilon > {0}$ then: Strong Triangle is false	2014	https://ieeexplore.ieee.org/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg	link
Disjunctive coBüchi Objectives	assume: Strong Triangle then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k\cdot n^{2})^{1-\epsilon})$-time algorithm for any $epsilon > {0}$ for generalized Büchi games. In particular, there is no such algorithm deciding whether the winning set is non-empty or deciding whether a specific vertex is in the winning set.	2016	https://arxiv.org/pdf/1607.05850.pdf	link
Disjunctive Reachability Queries in MDPs	assume: Strong Triangle then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm for any $\epsilon > {0}$ for target. The bounds holf for dense MDPs with $m=\Theta(n^{2})$	2016	https://dl.acm.org/doi/pdf/10.1145/2933575.2935304	link
Disjunctive Queries of Safety in Graphs	assume: Strong Triangle then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for disjunctive safety (objectives or queries) in graphs.	2016	https://dl.acm.org/doi/pdf/10.1145/2933575.2935304	link