Minimum Witness Finding

Description

Fix an instance of negative triangle with node sets $I, J, K$ and weight function $w$. Let $i \in I, j \in J, k \in K$. Recall that the triple $(i, j, k)$ is a negative triangle iff $(w(i, k) \odot w(k, j)) + w(i, j) < 0$. Fix a total ordering $<$ on the nodes in $K$ in the negative triangle instance. For any $i \in I, j \in J$, a node $k \in K$ is called a minimum witness for $(i, j)$ if $(i, j, k)$ is a negative triangle but $(i, j, k')$ is not a negative triangle for all $k' < k$ according to the ordering.

Minimum Witness Finding is the problem of finding a negative triangle $(i,j,k)$ such that $k$ is a minimum witness for $(i,j)$.

Related Problems

Subproblem: All Pairs Minimum Witness

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
Negative Triangle Detection	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