Find negative cycle with vertex constraints Given a graph with weighted edges, how can we find a negative cycle that contains at least one vertex in a given vertex set $\{V_1, V_2, \ldots, V_k\}$? Thanks.
If you don't require the cycle to be simple, then break the (directed) graph into its strongly connected components, and for each component containing one of the given vertices $V_i$, check whether the component contains a negative cycle.  If no component does, there is no negative cycle containing any $V_i$.  But if some component does, you can find a (non-simple) negative cycle containing $V_i$ by taking many copies of the negative cycle, and adding to that paths to and from some vertex in the cycle to $V_i$.  (The total time to find an implicit representation of the desired cycle will be the same as the time to find a negative cycle in a directed graph, e.g. $O(nm)$, if I recall.)

If you do require the cycle to be simple, then the problem becomes NP-complete, even if only a single vertex $V_1$ is given.  (You can reduce Hamiltonian Path to the problem: to find a Hamiltonian path from a given source $S$ to a given sink $T$ in a given graph $G$, give the existing edges weight -1, then add an artificial vertex $V_1$ with two edges of cost $N/2-0.01$ each, one from $V_1$ to $S$ and one from $T$ to $V_1$.)

If you allow the cycle to repeat vertices but not edges, I believe it is still NP-complete (by a similar reduction, but splitting each vertex $v$ into a directed edge $(v,v')$ in a standard way).