0
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

This is at most a proof sketch and not a complete proof. I think you can do a simple variation of DFS.

Run DFS from each important vertex. In each run, color some edges with red. The final red edges will be the edges that were colored with red in at least one run.

For a single DFS run, start from an important vertex $u$. Assume along the scan you reached another important vertex $v$, (where this is not necessarily the first time you reach $v$ in this run), then color all "stack-edges" by red.

I think on DFS as a recursive procedure, where this recursion defines a path, (I think Cormen calls it white path but I can never remember the colors...). I call the edges along this path "stack-edges".

I think the correctness can be proved using the properties of DFS.

For complexity, the complexity is $O(n\cdot k)$ for $k$ important vertices. No idea if it is optimal.

Does this problem have a name? It really reminds me of one of Tarjan's algorithms, but I can't remember which one.

I guess it is one of the four cited here: https://en.wikipedia.org/wiki/Tarjan%27s_algorithm

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .