We can phrase it as a decision problem in the following manner: Given V, f , and a threshold k, we wish to know if there is a set of edges E that respects transitivity and Yannakakis (1978) has shown that the simpler problem of finding in a graph G = (V , E ) a subset of edges A ⊆ E that respects transitivity and |A| ≥ k is NP-hard.
we can conclude that our optimization problem is also NP-hard by the trivial polynomial reduction defining the function f that assigns the score 0 for node pairs (u, v) / ∈ E and the score 1 for node pairs (u, v) ∈ E .