11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This question is pretty unclear. Weights on what, edges or vertices? What's $\{V_1, V_2, \dots, V_k\}$, is $V_1$ a vertex or a set of vertices? $\endgroup$ – Yixin Cao Jul 1 '12 at 7:59
  • $\begingroup$ @YixinCao Thanks for noting, edited: weight on edges, $V_1$ is a vertex. $\endgroup$ – Tianyi Cui Jul 1 '12 at 10:14
8
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ I like this answer much better than mine. $\endgroup$ – David Eppstein Jul 2 '12 at 16:19
6
$\begingroup$

I'm going to assume your input is a directed graph; I don't know how to do this for the undirected case.

Make $n$ copies of the vertex set of your graph, where $n$ is the number of vertices in the graph. Replace each edge from $u$ to $v$ in your original graph by edges that go from copy $i$ of $u$ to copy $i+1$ of $v$, for all choices of $i$. Additionally, if $u$ belongs to the specified vertex set but not otherwise, also include an edge that goes from copy $i$ of $u$ to copy $0$ of $v$.

The cycles in the expanded graph all project back down to cycles in the original graph, but every cycle in the expanded graph contains one of the specified vertices (otherwise you can't go backwards through the layers of expansion), so the original graph contains a negative cycle containing a specified vertex iff the expanded graph contains any negative cycle.

$\endgroup$
  • $\begingroup$ If the original graph has $n$ vertices and $m$ edges, the newly constructed graph will have $n^2$ vertices and $nm$ edges. Finding negative cycles in it will require $O(n^3m)$ time, which seems pretty large. I am still waiting for better solution, and thanks a lot! $\endgroup$ – Tianyi Cui Jul 2 '12 at 0:27
  • 2
    $\begingroup$ Possibly more problematic, the cycles it finds won't necessarily be simple. Do you require simple negative cycles? $\endgroup$ – David Eppstein Jul 2 '12 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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