在多项式时间内使用 DFS 的最小命中集算法

Question

我需要编写一个算法来找到给定无向图的最小命中集 F，即包含图的每个循环中的最小边的集合，使得 F 与任何给定循环的交集不为空.我写了一个算法，它使用深度优先搜索来查找图中所有可能的循环，然后在每个循环中取最小边并将其放入一个集合中（我在其中删除重复项）。

然而，我被要求在多项式时间内完成这个任务，我不太确定我的算法是否做到了。例如，我添加了一个计数器来解决以下从 A 开始的图形，我的 DFS 方法被调用了 34 次：

谁能帮我计算一下我写的算法的运行时间？它是功能性的，但似乎效率很低。谢谢

这是我的 DFS 方法的代码。 MHS 是像节点一样工作的基本数据结构。它们有一个标签和一个链接列表，其中包含一个端点（另一个节点）和一个与之关联的整数值）。 cycles 只是一个包含所有循环的 ArrayList，它们本身表示为边值的 ArrayList。

我使用了这篇 post 中描述的方法。

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;
    }
}

Answer 1

您真的是从找出图中的每个循环开始的吗？如果你有完整的图 Kn，其中每对节点都是连接的，那么每个节点的任意大小的有序集都定义了一个循环，所以有指数级的循环。

你可以试试

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

这应该是多项式时间，因为 while 循环的每次循环都会从图中删除一条边，迟早你会运行超出边。

但我不确定这是否回答了您的问题。我还注意到命中集合的标准定义是一个 NP 完全问题，通过集合覆盖 - https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation

Answer 2

事实证明，没有必要考虑图中的所有循环。我们可以简单地调整最小生成树的循环属性，表示循环中成本最高的边将不包含在 MST 中。同样的属性，而不是应用于最大生成树，告诉我们循环的成本最低的边将不包含在最大 ST 中。

为了解决这个问题，我们只需要找到G的最大ST（通过适配Kruskal的算法）和return G的所有没有被添加到树中的边。

在多项式时间内使用 DFS 的最小命中集算法

Minimum Hitting Set algorithm using DFS in polynomial time

java

algorithm

recursion

graph

depth-first-search