CODEWITHSUNDEEP
algorithmdata-structuresgraph
Joe C
Joe C

Reputation: 2827

Check if all given vertices are on a path

The problem is

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.

For example, if a set of vertices is {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

Here is a simple algorithm with complexity 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;
  }
}

The for-loop takes N step; the while-loop would visit all node/edge in the worst case with cost V + E.

Is there any known algorithm to solve the problem? If a graph is DAG, could we have a better solution?

Thank you

Upvotes: 2

Views: 576

Answers (2)

Erick G. Hagstrom
Erick G. Hagstrom

Reputation: 4945

You should check out the Floyd-Warshall algorithm. It will give you the lengths of the shortest path between all pairs of vertices in the graph in O(V3). Once you have those results, you can do a brute-force depth-first traversal to determine whether you can go from one node to the next and the next etc. That should happen in O(nn) where n is the number of vertices in your current set. Total complexity, then, should be O(V3 + N*nn) (or something like that).

The nn seems daunting, but if n is small compared to V it won't be a big deal in practice.

I can guess that one could improve on that given certain restrictions on the graph.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65506

Acyclicity here is not a meaningful assumption, since we can merge each strong component into one vertex. The paths are a red herring too; with a bunch of two-node paths, we're essentially making a bunch of reachability queries in a DAG. Doing this faster than O(n2) is thought to be a hard problem: https://cstheory.stackexchange.com/questions/25298/dag-reachability-with-on-log-n-space-and-olog-n-time-queries .

Upvotes: 1

Related Questions