Proof that the graph optimization problem is NP-hard
This problem is in P, it can be reduced to the Minimum cut problem.

The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$. 

The cost of the cut from source to sink in this graph with set of vertices $S$ along with source in one side of the cut exactly corresponds to your function $C$