Minimum Hitting Set algorithm using DFS in polynomial time

Question

I need to write an algorithm that finds the minimum hitting set F of a given undirected graph, i.e. a set containing the minimum edge in each cycle of the graph such that the intersection of F and any given cycle is not empty. I have written an algorithm that uses Depth First Search to find all the possible cycles in the graph, and then takes the min edge in each cycle and puts it in a set (in which i remove duplicates).

However, I was asked to complete this task in polynomial time, which I am not quite sure my algorithm does. For instance, I have added a counter to solve the following Graph starting on A and my DFS method gets called 34 times:

Could anyone help me figure the running time of the algorithm I wrote? It is functional but it seems to be very inefficient. Thanks

Here is the code form my DFS method. MHS are basic data structure that act like nodes. They have a tag and a list of links that contain an endpoint (the other node) and a integer value associated to it). cycles is simply an ArrayList containing all the cycles, which are themselves represented as ArrayLists of edge values.

I used the approach described in this post https://stackoverflow.com/a/549312/1354784.

public static void DFS(MHS v){
    ++counter;
    if(v.visited){
        MHS current=v.predecessor;
        ArrayList<Integer> currEdges=new ArrayList<Integer>();
        currEdges.add(getEdgeValue(current, v));
        while(!current.equals(v)){
            MHS p=current.predecessor;
            if(p==null)
                break;
            currEdges.add(getEdgeValue(p, current));
            current=p;
        }
        if(currEdges.size()>0)
            cycles.add(currEdges);
    }else{
        v.visited=true;
        for(int i=0;i<v.links.size();i++){
            MHS w=v.links.get(i).next;
            if(v.predecessor==null || !v.predecessor.equals(w)){
                if(v.visited){
                    MHS ok=w.predecessor;
                    w.predecessor=v;
                    DFS(w);
                    w.predecessor=ok;
                }else{
                    w.predecessor=v;
                    DFS(w);
                }
            }
        }
        v.visited=false;
    }
}

score 1 · Answer 1 · answered Feb 15 '16 at 05:54

Do you really start by finding every cycle in the graph? If you have the complete graph Kn, in which every pair of nodes is connected, then every ordered set of any size of the nodes defines a cycle, so there are exponentially many cycles.

You could try something like

While (there are any cycles left)
  Find a cycle
  find the shortest edge in that cycle
  remove that edge from the graph

Which should be polynomial time, because every trip round the while loop removes an edge from the graph, and sooner or later you will run out of edges.

But I am not sure if this answers your question. I note also that the standard definition of hitting set is an NP-Complete problem, via set cover - https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation

I think I figured it out. To get the hitting set I only need to consider the least edge in each cycle, so instead of finding all cycles in the graph, I think I can find the minimum spanning tree of the graph, and that these edges correspond to the ones I am looking for. — user1354784, Feb 16 '16 at 01:28

score 0 · Accepted Answer · answered Feb 16 '16 at 21:25

As it turns out, it wasn't necessary to consider all cycles in the graph. We can simply adapt the cycle property of minimum spanning trees that says that the most costly edge in a cycle will not be included in the MST. This same property, applied instead to a maximum spanning tree, tells us that the least costly edge of a cycle will not be included in the max ST.

In order to solve the problem, we only need to find the max ST of G (by adapting Kruskal's algorithm) and return all the edges of G that have not been added to the tree.

Minimum Hitting Set algorithm using DFS in polynomial time

2 Answers2