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

<p>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.</p>

CC BY-SA 3.0
2017-09-15T15:30:40.583Z
2017-09-15T15:30:40.583Z
user46256
<p>Recently I encountered an interesting graph problem and couldn't find proper solution: given undirected graph <code>G = &lt;V, E&gt;</code>, each vertex is either white or black. You need to find the path between given vertices <code>s</code> and <code>t</code> such that if <code>W</code> is the number of white vertices on that path and <code>L</code> is the length of the path, <code>W/L</code> is maximal possible. Obviously, the faster the algorithm is, the better.</p>

<graph-theory><graph-algorithms>
Algorithm finding path with maximal ratio of white vertices
Nikrom
# Algorithm finding path with maximal ratio of white vertices

(Asked by: username_0 on 2017-09-15)

Recently I encountered an interesting graph problem and couldn't find proper solution: given undirected graph `G =` , 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.

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2017-09-15. Score: 3

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.


---

