algorithm - 检查所有给定的顶点是否都在路径上

Question

问题是

Given a graph and N sets of vertices, how to check that if the vertices 
in each set exist on a path (that may not have to be simple) in the 
graph.

例如，如果一组顶点是 {A, B, C}

1) On a graph 
     A --> B --> C
   The vertices A, B and C are on a path

2) On a graph
     A ---> B ---> ...
            ^
     C -----+
   The vertices A, B and C are not on a path

3) On a graph
     A <--- B <--- ...
            |
     C <----+
   The vertices A, B and C are not on a path

4) On a graph
     A ---> X -----> B ---> C --> ...
            |               ^
            +---------------+
   The vertices A, B and C are on a path

这是一个复杂度为 N * (V + E) 的简单算法。

for each set S of vertices with more than 1 elements {
  initialize M that maps a vertice to another vertice it reaches;
  mark all vertices of G unvisited;
  pick and remove a vertex v from S;
  while S is not empty {
    from all unvisited node, find one vertex v' in S that v can reach;
    if v' does not exist {
      pick and remove a vertex v from S;
      continue;
    }
    M[v] = v';
    remove v' from S;
    v = v';
  }

  // Check that the relations in M forms a path 
  {
    if size[M] != size(S)-1 {
       return false;
    }
    take the vertex v in S that is not in M
    while M is not empty {
      if not exist v' s.t. M[v]' = v {
        return false;
      }
    }
    return true;
  }
}

for循环需要N步；在最坏的情况下，while 循环将访问所有节点/边，成本为 V + E。

有没有已知的算法可以解决这个问题？ 如果图是DAG，我们是否有更好的解决方案？

谢谢

Answer 1

这里的非循环性并不是一个有意义的假设，因为我们可以将每个强组件合并到一个顶点中。这些路径也是一个转移注意力的地方。对于一堆双节点路径，我们本质上是在 DAG 中进行一堆可达性查询。比 O(n²) 更快地执行此操作被认为是一个难题:https://cstheory.stackexchange.com/questions/25298/dag-reachability-with-on-log-n-space-and-olog-n-time-queries .