8
$\begingroup$

I'm having trouble understanding why it's easy to detect negative-weight cycles (Bellman Ford) but hard to find the maximum weight cycle in an undirected graph.

If we negate the weight of each edge, we can easily find if there are any cycles with total weight > 0. However it must not be easy to find if there are any cycles with weight > 1 or else we could repeat with 2, 3, 4 etc until the answer is no.

Is this correct? Why is it so much harder to detect if there exists a cycle with weight > 1 then to find if there is a cycle with weight > 0?

$\endgroup$
3
$\begingroup$

I don't think it's very surprising that finding a single negative-weight cycle is easier than finding the highest-weight cycle. If you ask me to find a negative-weight cycle, I can find any one and, if I give you what I claim is an answer, it's very easy for you to check the sequence of vertices and see that the weight really is negative. But the maximum-weight cycle feels like a very special object. Even if I claimed to have found it how would I convince you that there isn't another cycle with even higher weight?

On the other hand, maybe this intuition isn't helpful, since it's also trivial to check that a given cycle has weight at least 1 or 2 or 17...

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

This is an excellent question. I don't have a fully satisfactory explanation, but let me give you a start at it.

First off, it's important to understand that we can't solve this problem by simply enumerating all cycles and checking the weight of each one. Why not? Because there can be (and often are) exponentially many cycles. Therefore, merely enumerating them will necessarily take exponential time -- too long to be feasible.

So how does Bellman-Ford work? It works by some clever trick that avoids the need to individually examine each cycle one by one. Instead, it builds up a summary that summarizes something about the effect of all paths and cycles of length up to $n$. Effectively, for each vertex $v$, it summarizes all paths that start at $v$, end at $v$, and take at most $n$ steps. Since every cycle must contain a path of this form, the summary somehow encapsulates the effect of all possible cycles.

Why can't we use this to detect (say) whether there exists a cycle of weight $\ge 1$? It's because Bellman-Ford's summary includes paths that walk around the cycle multiple times. If the cycle is of length $k$, then it's gonna includes paths of length $n$, i.e., paths that walk around the cycle about $n/k$ times. For instance, if you have a cycle of length $n/3$, then the summary includes a path that walks around the cycle three times.

What's the effect of walking around a cycle multiple times? If you want to distinguish positive-weight cycles from cycles whose weight is not positive, walking around a cycle multiple times does no harm. If the cycle has positive weight, then you can walk around it a few times and the total weight will still be positive. If the cycle's weight is not positive, then you can walk around it a few times and the total weight will still be non-positive. So if all we care about is the difference between positive vs non-positive weight, walking around the cycle multiple times does no harm.

But now consider how things change if what we care about is the difference between "weight $\ge 1$" vs "weight $< 1$". If we have a cycle whose weight is $< 1$ and we walk around that cycle multiple times, the total weight might become $\ge 1$. For instance, if the weight of the cycle is $1/2$ and we walk around the cycle three times, then the total weight of that path is $1.5$, which is $\ge 1$: we started with a cycle of weight $< 1$ and ended up with a path of weight $\ge 1.5$. This fact totally screws up Bellman-Ford and makes it useless for checking whether there exists a cycle of weight $\ge 1$. (Do you see the difference?)

I realize this isn't a 100% satisfactory answer. It tells you why Bellman-Ford isn't going to work to solve your problem. However, it doesn't give you any intuition to explain why this is difficult in general (e.g., why it's hard to find some other algorithm to solve it). I don't have a really good intuition for that -- maybe someone else will have a better explanation for you. In the meantime, maybe this gives you a start at getting your head around why this problem is hard.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Deciding $weight \geq c$ is still easy for any constant $c$ and integer edge weights. I can check all cycles of length $c$ in $O(n^c)$ (assuming unit weights). But what if $c$ is not a constant, for example $c=n/2$? It wouldn't be polynomial anymore.

On the other hand with the general decision problem (i.e. when $c$ is not constant) we can decide the Hamiltonian cycle problem which is NP-Complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, but this doesn't give any intuition why it's hard to decide the general decision problem. Yes, there's a reduction to Hamiltonian cycle, obviously, but that doesn't give any intuition why. If you read the question, it's pretty clear the author is asking for intuition why this is hard when finding a positive-weight cycle is not hard. $\endgroup$ – D.W. Oct 26 '13 at 18:53
  • $\begingroup$ Yes I know that. The asker seems confused about the difference between deciding on a number and deciding on any given length. Please take a look at the question at the last paragraph. I'm trying to correct him on that part. Being harder or easier in terms of tractability depends on this distinction. $\endgroup$ – Parham Oct 26 '13 at 19:55
  • $\begingroup$ Checking all cycles of length $c$ also doesn't work if edges are allowed to have weight zero. OK, weight zero is often identified with there being no edge but it's easy to imagine applications where an edge with weight zero is not the same as no edge: for example, edges are segments of road and the weight is the toll that must be paid for that segment. $\endgroup$ – David Richerby Oct 26 '13 at 21:24
0
$\begingroup$

Let us consider the simpler versions of these problems where edges are unweighted.

  1. Given a graph $G$, check if $G$ has a cycle.

  2. Given a graph $G$ and a number $k$, check if $G$ has a cycle of length at least $k$.

The first one is easy and can be solved using DFS. The second one is NP-hard.


Let's look at an even simpler problem:

  1. Given a graph $G$ and two vertices $s$ and $t$, check if there is a simple path from $s$ to $t$ in $G$.

  2. Given a graph $G$ and two vertices $s$ and $t$ and a number $k$, check if there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

All of these problems are of the same flavor. The top one is easy while the bottom one is NP-hard. I will explain the difference for the last one because it is simpler but the same explanation applies to the other pairs.

The reason that the top ones are easy while the bottom ones are not is the result of the structure of the answers for these problems.

Let's first look at the problem of finding a simple path and try to solve it recursively. If we just try to solve this problem directly we would need to keep track of the vertices that we have used so far:

$SimplePath(s,t,G) :=$ there is a path from $s$ to $t$ in $G$.

$SimplePath(s,t,G)$ iff
$s=t$ or for some $u\in G$ $SimplePath(s,u,G-t)$ and $ut \in G$.

If we try to solve the problem with this naive recursive algorithm it will take exponential time: there exponentially many possibilities for the set of unused vertices! We have to be smarter.

Why did we get exponentially many possibilities? Because we were trying to find a simple path and to enforce this condition we needed to keep track of unused vertices.

OK, so let's drop that condition and see where we can get:

Consider the problem of a finding a path (not necessary simple) from $s$ to $t$. Since the path doesn't need to be simple we don't need to keep track of unused vertices. In other words, the graph doesn't change over time.

$Path^G(s,t) :=$ there is a path from $s$ to $t$.

$Path^G(s,t)$ iff
$s=t$ or
for some $u\in G$ $Path^G(s,t)$ and $ut \in G$.

But we are not done yet. The issue is that we don't know if $Path^G(s,u)$ is a smaller problem than $Path^G(s,t)$. So this recursive solution might end in a loop and never terminate.

To avoid this we can add an extra parameter that makes sure the problem gets smaller: the number of edges in the path.

$Path^G(s,t,k) :=$ there is a path from $s$ to $t$ with at most $k$ edges.

$Path^G(s,t,k)$ iff
$k=0$ and $s=t$ or
$k>0$ and for some $u\in G$ $Path^G(s,u,k-1)$ and $ut \in G$.

Now note that there is a simple path from $s$ to $t$ iff there is a path from $s$ to $t$ with at most $n$ edges. In other words:

$SimplePath(s,t,G)$ iff $Path^G(s,t,n)$.

The essential points here are:

  1. Every (nontrivial) simple path from $s$ to $t$ consists of a simple path from $s$ to some vertex $u$ and an edge $ut$.

  2. We can assume that $t$ does not appear in the simple path from $s$ to $u$.

  3. We don't need to explicitly keep the list of unused vertices.

These properties allow us to have a smart recursion for the existence of a simple path problem.

Now these do not apply to the problem of finding a path of length at least $k$. We don't know how to reduce the problem of finding a simple path of length at least $k$ to a smaller subproblem without keeping the list of unused vertices. Those properties allow us to solve the existence of path problem efficiently.

When a graph doesn't have a negative cycle they allow us to solve the existence of a path of length at most $k$ problem and the shortest simple path problems efficiently.

However they don't hold for the existence of a path of length at least $k$. Consider a graph with $3$ vertices $s, u, t$. $w(su) =1000, w(st) =1000, w(ut)=10, w(tu)=10$. The path of length at least $1001$ from $s$ to $t$ contains $u$ and the path of length at least $1001$ from $s$ to $u$ contains $t$. So we cannot reduce an instance of the problem to a smaller instance of the problem without explicitly giving the list of unused vertices.

In other words, we don't know a smart recursion for the existence of a simple path of length at least $k$ problem while we do know a smart recursion for the existence of a simple path.


Coming back to the last part of your question, there is problem with your argument.

It is indeed the case that the existence of a cycle of length $>k$ can be solved in polynomial time for any fixed $k$ (i.e. $k$ is not part of the input). (Similar to how one can check if an unweighted graph has a cycle of length $k$ in time $O(n^k)$.)

However when $k$ is part of the input this does not hold any more since the running time depends on $k$ in a bad way.

| cite | improve this answer | |
$\endgroup$

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.