Min weight feedback edge set with DFS

algorithms

Exercise from The Algorithm Design Manual

6-10. [4] Let G = (V,E) be an undirected graph. A set F ⊆ E of edges
is called a feedback-edge set if every cycle of G has at least one
edge in F.

(b) Suppose that G is a weighted undirected graph with
positive edge weights. Design an efficient algorithm to find a
minimum-weight feedback-edge set.

My proposed solution for (b) is to run DFS with getting max weight as the tie breaker. Then every back edge will always be the lowest weighted edge in its cycle. I'm wondering if this is a valid solution.

Best Answer

Here is how I would tackle this problem.

For simplicity, let's just assume that G is connected (The algorithm to be described below can be easily extended for the case when G is not connected).

First, for any feedback-edge set F, it must be true that the graph G' = (V, E-F) doesn't have any cycle. This follows directly from the definition of feedback-edge sets.

Since we are looking for the set F that has minimum total weight, G' should be a tree and the edges in G' must have the maximum total weight possible (why ?)
→ G' must be a maximum spanning tree.

So now the original problem is reduced to finding a maximum spanning tree. You may already know that the Kruskal's algorithm can be used for finding a minimum spanning tree. With a little modification, you can use Kruskal's algorithm to find a maximum spanning tree. https://stackoverflow.com/questions/4992664/how-to-find-maximum-spanning-tree

So in conclusion, the algorithm I just described has running time of O(E log V) time (which is just the running time of Kruskal's algorithm)

Related Solutions

Generic Adjacency List Graph implementation

Here's an implementation that I dug up from when I was dealing with graphs. Although it's in C#, with a few minor adjustments it could compile in Java.

To make it directed you would have to copy v.Adjacents.Add(new Edge(w, cost)); and reverse the direction, thereby taking up double the space.

I don't think it's any better than what you have though.

class Edge
{
    public Vertex Destination { get; set; }
    public double Cost { get; set; }

    public Edge(Vertex destination, double cost)
    {
        Destination = destination;
        Cost = cost;
    }

}

class Vertex
{
    public string Name { get; set; }
    public List<Edge> Adjacents { get; set; }
    public double Distance { get; set; }

    public Vertex(string name)
    {
        Name = name;
        Adjacents = new List<Edge>();
        Distance = double.MaxValue;
    }
}

class Graf
{
    private readonly Dictionary<string, Vertex> vertexmap = new Dictionary<string, Vertex>();

    public void AddEdge(string source, string dest, double cost)
    {
        var v = GetVertex(source);
        var w = GetVertex(dest);
        v.Adjacents.Add(new Edge(w, cost));
    }

    private Vertex GetVertex(string vertexname)
    {
        Vertex v;
        vertexmap.TryGetValue(vertexname, out v);
        if (v == null)
        {
            v = new Vertex(vertexname);
            vertexmap.Add(vertexname, v);
        }
        return v;
    }
}

Java – Which k-best shortest-path algorithms should I consider

To partially answer my own question:

Since posting this question, I discovered that we need to handle negative edge weights as well as positive (the limitation to acyclic / simple / loopless paths means that the best solution is defined, whereas without that limitation the shortest path through a graph with negative-cost cycles is undefined).

Yen's algorithm, and most of the others I examined, depend on a series of 1-best searches; most use Dijkstra for those intermediate searches. Dijkstra does not support negative edge weights, but we can substitute Bellman-Ford in its place (at least in Yen; presumably in Lawler or Eppstein as well). I've developed a modification of Bellman-Ford with a path-length limitation (in edges) and explicit cycle-checking during search (in place of the standard post-search cycle detection). The computational complexity is worse, but still tractable for my requirements. I'll edit this response and link to a tech report if I get permission to post it.

Best Answer

Related Solutions

Generic Adjacency List Graph implementation

Java – Which k-best shortest-path algorithms should I consider

Related Topic