A rare diary

It's long since my last diary written here but this is an important one. As some sort of researcher in the field of computational complexity, I ought to dig the SIMC problem out and make an in depth analysis on it, in particular the complexity classification, and algorithm solving them.

Allow me to brief the problem here.

In the graph, assume every edge has weight 1 that the distance can be calculated accordingly. We also define the distance between edges and vertices. For $e = (u,v) \in E$, $d(e,w) = 0.5 + min(d(u,w), d(v,w))$ and the distance between edges immediately follows. It is clear that the distance measurement is metric. (why?)

For a graph $G = (V,E)$ with two disjoint sets of vertices $V_s, V_c$, define score to be the number of edges closer to $V_c$. i.e. $d(e, V_c) \leq d(e, V_s)$. If the distances are equal it counts as 0.5.

Let's have a function to describe the score: $f(G, V_s, V_c) =~score$.

Instance: $G = (V,E)$ and two disjoint sets of vertices $V_s, V_c \subseteq V$, with some further constraint specified upon the challenge.
Output: Another set $V_{c'}\subseteq V$ that is mutually disjoint with $V_s, V_c$.
Goal: Maximize $f(G,V_s, V_c \cup V_{c'})$.

Maybe you have already heard it before, that Greedy algorithm works really well for this problem. Is it the best solution? It is clear that the greedy algorithm is a polynomial time algorithm. Then is this problem in P? Is it NP? This will be an exciting review of the old problem.