-2
$\begingroup$

Recently I encountered an interesting graph problem and couldn't find proper solution: given undirected graph G = <V, E>, each vertex is either white or black. You need to find the path between given vertices s and t such that if W is the number of white vertices on that path and L is the length of the path, W/L is maximal possible. Obviously, the faster the algorithm is, the better.

$\endgroup$
3
$\begingroup$

This problem is NP-hard, by the following reduction from the Longest Path Problem:

Color every vertex white but s and t. Then any s-t-path with W white vertices has length W+1, so it maximizes W/L = W/(W+1) if and only if it is a longest s-t-path.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.