2
$\begingroup$

The definition of "Single Connected" is that for every $u,v \in V$ there is at most a single simple path from $u$ to $v$, and at most a single simple path from $v$ to $u$.

The objective is to find an efficient algorithm to decide whether the graph is "single connected".

I've managed to come up with the following algorithm:

for all v in V:
      Perform DFS(v)
      for all e in E, check if:
          there is a forward edge
          there is a cross edge

if there is a forward edge/cross edge, we have found another simple path between $u$ and $v$, therefor the graph is not single connected.

This algorithm runs in $O(|V| \cdot (|V|+|E|))$ which is okay, but according to a colleague, this is solveable in linear time.

The most I've been able to think of is using tarjan's algorithm to reduce the graph to a DAG , however I am unsure on how to proceed from there.

I've also managed to find this question:

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

yet it remains unanswered.

$\endgroup$
3
  • $\begingroup$ Shouldn't the condition be "exactly one path"? $\endgroup$ Commented Dec 27, 2022 at 23:53
  • $\begingroup$ What is a "simple path" for you? $\endgroup$ Commented Dec 28, 2022 at 4:52
  • $\begingroup$ The condition stated in the problem is “at most one simple path”. the definition of simple path is as usual: no cycles, no repeating vertices/edges. $\endgroup$
    – Aishgadol
    Commented Dec 28, 2022 at 9:28

1 Answer 1

2
$\begingroup$

Is your graph directed or undirected?

If your graph is undirected then the condition you mention is equivalent to your graph being a forest (every connected component is a tree).

$\endgroup$
3
  • 2
    $\begingroup$ Consider a directed graph with edges $\overrightarrow{12},\overrightarrow{13},\overrightarrow{42},\overrightarrow{43}$. It is "single connected". Is the corresponding undirected graph a forest? $\endgroup$
    – John L.
    Commented Dec 27, 2022 at 22:05
  • $\begingroup$ A directed cycle is not singly connected — there are two simple paths from $1$ to itself. $\endgroup$ Commented Dec 28, 2022 at 4:51
  • $\begingroup$ Apologies for not mentioning, the graph were trying to decide whether it is “single connected” is directed. $\endgroup$
    – Aishgadol
    Commented Dec 28, 2022 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.