-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$

closed as off-topic by Kaveh, András Salamon, Yuval Filmus, Hsien-Chih Chang 張顯之, Lev Reyzin Sep 20 '17 at 17:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, András Salamon, Yuval Filmus, Hsien-Chih Chang 張顯之, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

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.

$\endgroup$

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