How can I determine which edges are part of simple paths between a vertex subset?

user_8008396 0
Viewed 131

Problem:

  • I have an undirected graph (with cycles) given by a list of edges.
  • I'm given a list/subset of vertices/nodes (example: [0, 9, 17] below), which I refer to as "important vertices".
  • I want to color each edge based on whether it is part of some simple path [1] between the important vertices. In the example below, I have colored the edges red if they are part of such a simple path, and blue otherwise.

Visualization of coloring result

[1]: a simple path means any vertex can appear at most once in the path.

Questions:

  • Does this problem have a name?
  • Are there any existing algorithms that solve this problem?
  • What is the optimal time comlexity? My gut feeling tells me it might be possible to solve this by visiting every edge a constant number of times. Once you know whether an edge is part of a simple path or not, you probably don't need to visit it again.

What I've tried so far:

  • For every edge, perform a depth-first search in both directions to find out which important vertices are reachable through simple paths in both directions.

  • If either of the directions don't reach an important vertex, or only the single and same important vertex is reached in both directions, the edge will color itself blue - otherwise it will color itself red.

  • This almost works - but mistakenly colors the 15-16 edge red - and seems to scale really poorly, which is why I'm looking for a better way to do this.

Related:

I don't consider this question to be a duplicate of the above, since this is about an arbitrary number of "important vertices", and about classifying all edges, rather than a single one.

graph-theory algorithm
3 Answers

Assuming your graph is connected, start with any spanning tree in blue. There will be one path through all of the important vertices, re-colour this red.

Example graph.

Any uncoloured edge forms a loop. If a loop has any edges that are red, re-colour it red, including the uncoloured edge. Go repeatedly through all the uncoloured edges until you cannot colour a loop red. Then, colour the remaining edges blue.

Complete.

I think this works; because the red edges are necessarily connected.

user_24728270

It looks like you want yo find biconnected components. They form a tree (forest if the graph is not connected; in this case handle each tree separately). Then colour some edges and vertices of that tree red.

Articulation vertices of the original graph correspond to tree vertices, and biconnected subgraphs correspond to tree edges.

If an important vertex is an articulation vertex, colour it red.

If a biconnected component has any important vertices which are not articulation vertices, colour the corresponding tree edge and both its vertices red.

If there is a path between two red vertices of the tree, colour the entire path (edges and vertices) red.

Repeat until there is no more edges or vertices to colour.

There seems to be a single exceptional case in the algorithm above, namely when there is a single important vertex in a (simply connected) component. It is easy to detect and handle separately.

user_7758060

So it turns out this problem becomes simpler if I focus on which vertices are part of simple paths, rather than edges. I'll name these "connecting vertices". Any edge with a "connecting vertex" in each end is part of some simple path between important vertices.

(with the exception of edges with the same vertex in both ends. This type of edge will never be part of any simple path)

I ended up with an algorithm which is similar to biconnected components, but different in what it tracks as it traverses the trees/forest. I believe it has linear time complexity (O(V+E)).

I've implemented it in Python/numpy below as a depth-first search.

import numpy as np

def is_connecting_vertex(get_neighbors, important_vertices, vertex_count):
    visited = np.zeros(vertex_count, dtype='bool')
    parent = np.zeros(vertex_count, dtype='int64')
    last_important = np.zeros(vertex_count, dtype='int64')
    is_important = np.zeros(vertex_count, dtype='bool')
    is_connecting = np.zeros(vertex_count, dtype='bool')
    
    stack = []
    for v in important_vertices:
        parent[v] = v
        last_important[v] = v
        is_important[v] = True
        is_connecting[v] = True
        stack.append(v)
    
    while len(stack):
        v = stack.pop()
        if visited[v]:
            continue
        visited[v] = True

        if is_important[v]:
            p = parent[v]
            while not is_connecting[p]:
                is_connecting[p] = True
                p = parent[p]
        else:
            last_important[v] = last_important[parent[v]]

        for child in get_neighbors(v):
            if not visited[child]:
                parent[child] = v
                stack.append(child)
            elif last_important[child] != last_important[v]:
                is_connecting[v] = True
                p = parent[v]
                while not is_connecting[p]:
                    is_connecting[p] = True
                    p = parent[p]
    
    return is_connecting

Thanks to both n. 1.8e9-where's-my-share m. and Neil for putting me on the right track with their answers.

user_80083960
Related