All Pairs Minimum Witness

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.

All Pairs Minimum Witness (APMW) is the problem of finding a minimum witness $k$ for each pair $(i,k)$ if such a $k$ exists for $(i,j)$.

Related Problems

Generalizations: Minimum Witness Finding

Parameters

$n$: number of vertices

$m$: number of edges

Table of Algorithms

Currently no algorithms in our database for the given problem.