Detecting negative cycles in an undirected graph
Lance Fortnow
Given a undirected graph with positive and negative edge weights, does there
exist a simple cycle with negative total weight?
What if we assume the graph is planar?
Mohammad Mahdian
For more details, see the book "Intro to Algorithms" by Leiserson et al.
(after Bellman-Ford's alg).
--Mohammad
Daniel A. Jimenez
Maybe both :-)
>Given a undirected graph with positive and negative edge weights, does there
>exist a simple cycle with negative total weight?
>
>What if we assume the graph is planar?
The Bellman-Ford algorithm (for the single-source-shortest-path problem)
is capable of detecting negative weight cycles. It seems that this should
work for simple cycles. This sounds simple; am I missing something?
--
Daniel Jimenez djim...@cs.utexas.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
Mohammad Mahdian
>
> Lance Fortnow <for...@research.nj.nec.com> wrote:
> : Is the following problem in P or NP-complete:
> : exist a simple cycle with negative total weight?
>
> from u to w in an undirected graph G without negative-cost cycles.
> The algorithm can be used to solve your problem. I am sure you
> can figure out the details.
>
> 1. Construct a bipartite graph B=(V,V',A) as follows. Create two copies
> of the vertices of G: V and V'. Remove w from V, remove u' from V'.
> For each edge (x,y) in G, add the edges (x,y') and (y,x') with the
> same weight as (x,y). Also, add edges of the form (x,x') with zero weight.
>
> 2. Find a minimum-weight perfect matching M in B. The edges of M with
> non-zero weight generate a path between u and w of the same total
> weight as M.
>
> This procedure fails if there are negative-weight cycles because the
> final result may be a path from u to v and some independent cycles.
> Therefore the weight of the path may not be the same as the weight of M.
>
> Regards,
> Balaji Raghavachari
> ----------------------------------------------------------------------------
> Balaji Raghavachari Phone : (972) 883-2136
> Associate Professor, Computer Science Fax : (972) 883-2349
> University of Texas at Dallas Email : r...@utdallas.edu
> Richardson, TX 75083-0688 http://www.utdallas.edu/~rbk
I think this does not solve the problem in the presence of negative
edges,
because if the weight of the edge xy in the original graph is negative,
the perfect matching can be a path from u to w plus the edges (x,y') and
(x',y).
--Mohammad
Kevin Wayne
Daniel A. Jimenez <djim...@cs.utexas.edu> wrote:
>In article <1VHj5.114055$lU5.7...@news1.rdc1.nj.home.com>,>Maybe both :-)
>
>>Given a undirected graph with positive and negative edge weights, does there
>>exist a simple cycle with negative total weight?
>>
>
>The Bellman-Ford algorithm (for the single-source-shortest-path problem)
>is capable of detecting negative weight cycles. It seems that this should
>work for simple cycles. This sounds simple; am I missing something?
Yes, I think the poster is interested in undirected graphs.
The problem of finding a shortest path with no negative cycles is in P for
general undirected graphs, but as far as I know, you need to use matching
techniques to solve it. Presumably, if there are negative cycles, the algorithm
fails and you can recover a certificate explaining why (as in Bellman-Ford).
Cheers,
Kevin
--
Kevin Wayne I believe virtually everything I read.
35 Olden Street
Princeton, NJ 08544 -David St. Hubbins
Kevin Wayne
Balaji Raghavachari <r...@utdallas.edu> wrote:
>Lance Fortnow <for...@research.nj.nec.com> wrote:
>: Is the following problem in P or NP-complete:
>: exist a simple cycle with negative total weight?
>
>
>from u to w in an undirected graph G without negative-cost cycles.
>The algorithm can be used to solve your problem. I am sure you
>can figure out the details.
>
>1. Construct a bipartite graph B=(V,V',A) as follows. Create two copies
> of the vertices of G: V and V'. Remove w from V, remove u' from V'.
> For each edge (x,y) in G, add the edges (x,y') and (y,x') with the
> same weight as (x,y). Also, add edges of the form (x,x') with zero weight.
>
>2. Find a minimum-weight perfect matching M in B. The edges of M with
> non-zero weight generate a path between u and w of the same total
> weight as M.
>
>This procedure fails if there are negative-weight cycles because the
>final result may be a path from u to v and some independent cycles.
>Therefore the weight of the path may not be the same as the weight of M.
>
>Regards,
>Balaji Raghavachari
>----------------------------------------------------------------------------
>Balaji Raghavachari Phone : (972) 883-2136
>Associate Professor, Computer Science Fax : (972) 883-2349
>University of Texas at Dallas Email : r...@utdallas.edu
>Richardson, TX 75083-0688 http://www.utdallas.edu/~rbk
Balaji Raghavachari
Kevin Wayne
David A. Wagner <d...@blowfish.isaac.cs.berkeley.edu> wrote:
>Lance Fortnow <for...@research.nj.nec.com> wrote:
>> interested in the undirected case. The usual reduction from undirected to
>> directed (by replacing every undirected edge between two vertices by two
>> directed edges) won't work here because I do not want to allow using the
>> same undirected edge twice.
>
>That doesn't seem to be a problem, because any negative-weight cycle
>in the constructed directed graph G' can be transformed into a simple
>negative-weight cycle in the original undirected graph G. If there
>is any repeated vertex v, you can decompose the cycle into a list of
>component cycles, each of which traverses v exactly once. So pick one
>with negative weight (they can't all have non-negative weight), and
>repeat the decomposition until you get a negative-weight cycle which
>traverses each vertex at most once. This is the cycle you wanted.
>
>Am I missing something?
Yes, consider the undirected graph consisting of 2 vertices and 1 negative
weight edge connecting them. Your algorithm with claim it has found a
negative cost cycle.
Regards,
Kevin
David A. Wagner
Lance Fortnow
Jeffrey Considine
> Is the following problem in P or NP-complete:
> Given a undirected graph with positive and negative edge weights, does there
> exist a simple cycle with negative total weight?
It's in P. The basic idea is to check for shortest paths and pay attention
for negative distances. Bellman-Ford checks this for single source but you could
probably run an all-pairs shortest paths algorithm and then check for negative
distances more cheaply.
> What if we assume the graph is planar?
Still in P, of course.
jef
--
Jeffrey Considine
Head Terminal/Programming Assistant
CAS Undergraduate Computer Science Lab
Boston University
Kevin Wayne
>>: Is the following problem in P or NP-complete:
>>: Given a undirected graph with positive and negative edge weights, does there
>>: exist a simple cycle with negative total weight?
>>
>>
>>from u to w in an undirected graph G without negative-cost cycles.
>>The algorithm can be used to solve your problem. I am sure you
>>can figure out the details.
>>
>>1. Construct a bipartite graph B=(V,V',A) as follows. Create two copies
>> of the vertices of G: V and V'. Remove w from V, remove u' from V'.
>> For each edge (x,y) in G, add the edges (x,y') and (y,x') with the
>> same weight as (x,y). Also, add edges of the form (x,x') with zero weight.
>>
>>2. Find a minimum-weight perfect matching M in B. The edges of M with
>> non-zero weight generate a path between u and w of the same total
>> weight as M.
>>
>>This procedure fails if there are negative-weight cycles because the
>>final result may be a path from u to v and some independent cycles.
>>Therefore the weight of the path may not be the same as the weight of M.
Sorry, I think my last message got chopped. Anyway, the above reduction does
not seem to work for undirected graphs, because there is nothing preventing
the matching from taking both (x, y') and (y, x').
See Section 12.7 in Ahuja, Magnanti, Orlin for a cute reduction (due to
Edmonds) from the shortest path problem in undirected graphs to weighted
nonbipartite matching.
Cheers,