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

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中进行一堆可达性查询。要比0 (n²)更快地完成此操作被认为是一个难题:https://cstheory.stackexchange.com/questions/25298/dag-reachability-with-on-log-n-space-and-olog-n-time-queries .

Answer 2

你应该看看Floyd-Warshall算法。它会给出O(V³)中所有顶点对之间的最短路径的长度。一旦你有了这些结果，你就可以进行深度优先遍历，以确定你是否可以从一个节点到下一个节点，等等。这应该发生在O(nⁿ)中，其中n是当前集合中的顶点数。那么，总复杂度应该是O(V³ + N* N ^N )(或类似的值)。

nⁿ看起来令人生畏，但如果n比V小，在实践中就不是什么大问题了。

我可以猜测，在给定图形的某些限制条件下，可以对其进行改进。