4
$\begingroup$

What is supposed to be the right result of an SCC algorithm running on a DAG. should it return "no components" or "there are V components of size 1"?

I suspect it will return the latter (since it will start with the last sink, and then go back and mark each single sized vertex as a component, since each DFS will be of a single node before it can continue)

But is this a convention? E.g. if a treat SCC as a "great way to find if a graph has cycles" then I would expect it to return an empty result if there are none. e.g. components of size 1, who don't have a self-loop, don't really "go from A to A". is there a SCC variant that is more explicitly "find all groups that has cycles in them"? (e.g. is there a named variation)

Or what I'm looking for is basically "run SCC, then remove all components of size 1, and you got yourself a cycle detector, e.g. if after you do that you end up with no components, then your graph is a DAG"

Is there a name for that special SCC case? (assuming my understanding in the beginning of the question is correct)

$\endgroup$
2
$\begingroup$

I know of no convention; the right result depends entirely on what you want to do with the result. As an example, if you're trying to use strongly connected components to find satisfying assignments for 2SAT instances, then you likely want all the singleton cycles returned along with the larger components. But if you're just trying to find out if a graph contains a cycle, then the singletons won't be of interest to the caller so the SCC function could usefully omit returning them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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