algorithm - 图寻路算法变体

Question

我正在寻找一个算法，它以一个无向图作为输入，并找到一个子集的顶点，使这些顶点诱导的子图形成一个连接的无环树。
例如，在下图中，“X”节点将创建一个有效的解决方案，但包含任何“O”节点都将使其无效。

    O
   /|
O-X-X-X
 \ /
  X-X

对我来说，解决方案的有用性与子集的大小成比例。虽然我不需要整个最大子集，但近似近似是非常有用的。
我尝试了一种显而易见的算法，从一个随机节点开始，如果不诱导循环，则添加相邻的顶点。然而，我有一种感觉，这会产生非常次优的树。
我应该提到的是，我的特定应用程序包含大约100个节点和大约1000条边的图。这是足够小的暴力回溯算法可能是可行的，如果实施良好（例如，使用Dancing Links，但我还没有尝试过。

Answer 1

这个问题被称为非常类似于Feedback Vertex Set，不幸的是它是NP难的根据维基百科页面，最著名的近似算法具有approximation ratio 2：Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem."。
“连通反馈顶点集”的np-硬度证明
我忽略了结果图需要连通的条件，这不是反馈顶点集（fvs）的情况。下面我将展示您的问题，我将称之为连接反馈顶点集（cvfs），不过是np难的。
给定一个FVS的实例（G=（V，E），k），我们需要构造一个CFVS的实例（G'=（V'，E'），k'），其属性是（G，k）是FVS的YES实例，前提是（G'，k'）是CFVS的YES实例非正式地说，这个G'看起来像G的“一堆副本”，有一些额外的顶点和边我们这样做：
对于v中的每个顶点v_i，创建v中的v_v_顶点v_i_j，1<=j<=v的路径（不是我在评论中最初说过的团）。这些是“肉顶点”。（你可以想象顶点v''u i''j在“层”j中）顶点v''u i''u 1，v''u i''u 2，…，v''u i''v''v是与顶点v''i在g中对应的肉的“链”（是的，可怕的名字…）。
对于E中的每个边（v|i，v|j），在G'中相应顶点之间创建所有对应的“平行”边——即，创建边（v|i|u 1，v|u j|u 1），（v|i|u 2，v|u j|u 2），…，（v|u i|v|，v|u j|v）（这些边都连接同一层中的顶点。）
对于v中的每个顶点，也要创建一个额外的“骨架顶点”u“u i in v”。把这个U'u I和V'u I'u 1相邻。
将另一个顶点r添加到v'，并使其与每个骨架顶点u''u i相邻。
最后，设置k'=v*k+v-1。
首先，我将展示如果fvs实例（g，k）是yes实例，那么（g，k’）是问题的yes实例。设X是FVS实例（G，K）的任何解（即删除顶点集），它留下至少1个G未被删除的顶点（这样的解必须存在，因为1-顶点图不包含循环）；然后我们可以构造一个解X’到你的问题的实例如下：
对于在FVS解X中删除的每个顶点v|i，我们可以从G'中删除相应的路径v|i|u 1，…，v|i|v |，总代价最多为| v |*k（删除每个路径需要| v |顶点删除，并且最多k个顶点被X从G中删除）这保证了不存在仅由g'-x'中的肉顶点组成的循环（如果存在，这将与fvs解决方案x到（g，k）的可行性相矛盾）。
对于fvs解x中的每个连通分量，我们可以删除g'中除1个外的所有对应骨架顶点。我们在G'中剩下的是一堆FVS解决方案G-X的| V |副本，加上该解决方案每个组件的单个骨架顶点，再加上根顶点r。由于我们只有一条从每个连接组件（通过每个组件的单个骨架顶点）到r的路径，因此G'中不可能有循环由于g-x至少包含一个连接组件，这可能涉及最多v-1个删除，因此总体上最多需要v*k+v-1个删除，因此构造的cfvs实例（g'，k'）的答案是yes。
其次，我将展示如果问题的构造实例（G'，k'）是YES实例，那么FVS的原始实例（G，k）是YES实例。
设X'为cfv的构造实例（G'，k'）的任意解（即删除顶点集）考虑由g'-x'中的每一层肉顶点所诱导的子图：有v这样的层。一般来说，不同的层可以包含不同数量的删除。选择任何包含最小删除数的层j；因为g'-x'是无循环的，所以每个诱导子图也是无循环的，特别包括层j。层j中的删除数最多为k'/v，因为否则（通过j的最小选择）总体上将严格超过k'删除，这是一个矛盾。但是，任何整数<=k'/| V |必须<=RoundDown（（| V |*k+| V |-1）/| V |）=k，并且层j只是原始FVS问题（G，k）的副本，因此有可能破坏层j中的每个循环，因此在原始FVS实例（G，k）中最多有k个删除这意味着（g，k）是fvs的yes实例。
（g，k）是fvs的yes实例意味着（g'，k'）是cfvs的yes实例，反之亦然，因此（g，k）是fvs的no实例意味着（g'，k'）是cfvs的no实例，因此问题实例是等价的。显然（g'，k'）可以由（g，k）在多项式时间内构造，因此cvfs是np难的。这显然也是np完全的，因为对yes实例的解决方案可以在o（v+e）时间内用单个df检查正确性（即循环自由度和连通性）。