If every strongly connected component in a graph has only one incoming edge each from outside the component, is that a necessary and sufficient condition for the whole graph to be reducible? I have seen this definition in this post, but I do not seem to find other references to this characterisation. For reference, I have been reading Steven Muchnik's Compiler Design book.
In addition, if there are any other references to this characterisation, I'd be very grateful.
If every strongly connected component in a graph has only one incoming edge each from outside the component, is that a necessary and sufficient condition for the whole graph to be reducible?
It's a necessary condition, but not a sufficient one. (I'll give a counterexample below.)
I have seen this definition in this post, [ā¦]
Unless I'm missing something, that's not true; that post doesn't use the term "strongly connected component", and doesn't say anything equivalent to that.
Rather, that post says that a flow graph is reducible if no strongly connected subgraph has two entries. That's a much stronger criterion, because every strongly connected component is a strongly connected subgraph, but not every strongly connected subgraph is a strongly connected component.
For a concrete counterexample, consider the flow graph with four nodes 0, t, u, and v, where 0 is the initial node, and there are edges from 0 to t and in both directions between all three of t, u, and v. This graph is not reducible, but it satisfies the (incorrect) characterization that you ask about. It doesn't satisfy the (correct) characterization from the post you link to, because there are two entries to the strongly connected subgraph uāv.