Minimum Witness Finding (Minimum Witness)
Revision as of 10:29, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE:Minimum Witness Finding (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,...")
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 |