In weighted undirected graph, how to find the mini

Question

Suppose we have a weighted undirected graph, and the number of edge |E| is about k times of node number |V|, i.e, |E| ~= k * |V|.

Now, one node, say v, is choosen, and we want to find the cycle containing v with the minimum average cost. (i.e., average cost means average edge weight along a cycle.)

Is there any efficient algorithms?

Sorry, I missed one point-the cycle do not need to contain all nodes in this Graph. This makes it different from Hamilton cycle problem.

Answer 1

Dvorak's answer is correct. The original question requires the cycle to pass through a specified vertex v. A cycle with average cost (v+2)/v will be the optimal answer to the problem "Find the simple cycle with minimum average cost which must pass through vertex v".

In Karp's paper, the problem "Find the minimum mean cost cycle in the graph" is solved in O(|V||E|). The cycle need not pass through any specific vertex.

Answer 2

This is equivalent to the Hamiltonian cycle problem, which is NP-complete. There is no worst-case-polynomial algorithm able to solve this unless P = NP.

We can reduce the hamiltonian cycle problem to this problem:

• choose an arbitrary vertex as the starting point
• assign the cost of 2 to every edge incident to this vertex
• assign the cost of 1 to all other edges

the average cost of an n-cycle is (n+2)/n - a decreasing sequence for positive n. For a v-vertex graph, there is a cycle of the average cost of (v+2)/v iff the graph is a hamiltonian graph. Since the determination if a hamiltonian graph is NP-complete, this problem is NP-hard.

The decision problem associated with this problem ("Is there a simple cycle of an average edge cost of x passing through a vertex V") is in NP: if a path of that average length exists, then verifying that a cycle is a valid cycle with low enough average cost takes O(v) time (using an adjancency matrix representation).

---

Thus, you cannot hope for a worst-case-polynomial-time algorithm. But, depending on the distribution of edge costs, the branch-and-bound algorithm or branch-and-bound with dynamic programming can be very efficient:

• (optional) Remove all vertices that are not a part of a 2-vertex-connected component that V is (V can lie in multiple 2-vertex-connnected components).
• Enumerate all paths from V. Let the associated priority queue be q:
  • Start with the empty path.
  • Pick the path with the lowest cost estimate (lower bound). In case of a tie, pick the path added the latest.
  • Add this paht to the "done" set.
  • If the cost estimate is not lower than c_best, terminate the loop. Else,
  • Try every outgoing edge:
    • If the new vertex is already in the path and (it is not V or the new path would be a two-cycle⁺), reject this edge. Else,
    • Extend the path with this edge and compute the cost estimate of this new path.
    • If the estimate is not lower than c_best, reject this path. Else,
    • If the last vertex is V, set c_best_path to this path and c_path to its cost.
    • Else if a path with the same set of visited vertices and the same last vertex (= signature) is not already present in the "done" set, add the new path to q.
    • If the path being added has the same signature as another path in the queue remove the more expensive path from the queue.
• Return c_best_path

⁺: if the graph is a multigraph, you need to to take two cheapest parallel edges rather than the same edge twice. This is probably best handled in a separate step.

Dynamic programming checks can be very cheap (just hash a vertex set with a vertex) but if there are very few expected saves (the algorithm is likely to end early), it can be left out - drop the "done" set and ignore any duplicates (different paths with the same signature) in the queue.

This algorithm works just as fine for any path cost metric as long as you can compute a lower bound. For the average-edge-cost problem, I can think of several heuristics:

In any case, if the path is a cycle, compute and return its exact cost.

One simple heuristic is to assume that you may be able to visit all remaining vertices with edges no cheaper than the cheapest path in the entire graph or 2-connected component. Then the respective expected cost is (cost + (v - edge_length) * c_min) / edge_length. The upside is this is fast to compute. The downside is that if the graph is big and there are few edges nearly as cheap as the cheapest one, then this algorithm could expand a lot of paths to reach the "oasis" it thinks there is.

If there are few edges as cheap as the cheapest one, you can prepare a list of v lowest costs among all edges in the graph. Then to estimate the cost of a graph, consider: The path completed with only the cheapest edge, the path completed with the cheapest two edges, the path completed with the cheapest three edges... while(exp_cost_decreases && length < v) exp_cost = (exp_total_cost += best_edges.next) / ++length. The upside is it makes better guesses. The downside is that it takes longer to compute if there are lot of edges that lower the estimate.

You always have to use either a common edge to the start vertex and the end vertex of the path (if one exists) or one of the edges adjanced to each vertex (min_cost_adjanced(V) + min_cost_adjanced(end)). If a common edge is found, the handling of cycles should possibly be done here.

In case of the hamiltonian cycle reduction, both of the first two heuristics will perform equally poorly. The heuristics (1+3) and (2+3) will perform equally. The best-case scenario is linear in time. The worst-case scenario is O(v*k*2^v) with dynamic programming or O(v*k*log(k)*k^v) without (assuming a priority queue with O(log n) push, pop-min and decrease-key)

Note that the best known algorithm to test whether a hamiltonian cycle exists in a general graph is O(1.657^v) (according to wikipedia, as of Aug 2013)

Answer 3

There actually exists an O(|V||E|) algorithm, based on dynamic programming, first described by Karp in 1978 (http://www.sciencedirect.com/science/article/pii/0012365X78900110, or Section 5.7 in "Network Flows" by Ahuja, Magnanti, and Orlin).

The reduction given by Jan is, unfortunately, incorrect, because a cycle of cost (v+2)/v will in general not be the minimum mean cost cycle. In particular, any cycle that does not contain the starting point will have mean cost 1 < (n+2)/n for any n.