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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Shouldn't the condition be "exactly one path"? $\endgroup$
    – Paŭlo Ebermann
    Dec 27, 2022 at 23:53
  • $\begingroup$ What is a "simple path" for you? $\endgroup$
    – Yuval Filmus
    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
    Dec 28, 2022 at 9:28

1 Answer 1

Reset to default
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).

Improve this answer
$\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.
    Dec 27, 2022 at 22:05
  • $\begingroup$ A directed cycle is not singly connected — there are two simple paths from $1$ to itself. $\endgroup$
    – Yuval Filmus
    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
    Dec 28, 2022 at 9:04

Your Answer

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

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