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.

## No comments:

## Post a Comment