# What is a reducible flow graph?

What is a reducible flow graph? sorry if this is a stupid question but I'm having trouble finding an answer.
Also multiple equivalent definitions and some motivation would be nice too.

• Googling "reducible flow graph" seems to give a lot of relevant hits. – David Richerby Feb 14 '18 at 18:57
• en.wikipedia.org/wiki/Interval_(graph_theory) – D.W. Feb 14 '18 at 19:49
• I've found weird definitions like A flowgraph is reducible when it does not have a strongly connected subgraph with two (or more) entries which I believe should be equivalent to being acyclic??? Or a flowgraph is reducible if Every back edge has its source dominated by its target, for all DFS trees I also don't understand this definition wouldn't every edge have it's source dominated by it's target by definition? – Hao S Feb 14 '18 at 23:40

This blog post summarises the situation well my opinion, but let me go through some of your concerns:

Reducible is NOT equivalent to acyclic: consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with a loop from $z$ to $y$. Then there is an SCC $\{y,z\}$ so it is not acyclic. But it is reducible because the SCC $\{y,z\}$ has a single entry point y. Notice how this corresponds to a program with a while/for loop. On the other hand, if you consider a path $x\rightarrow y\rightarrow z\rightarrow w$ with again a loop $z\rightarrow y$ but also a forward jump $x\rightarrow z$. Not this is not reducible anymore because the SCC $\{y,z\}$ has two entry points: $y$ can be entered from $x$, but $z$ can also be entered from $x$. This intuitively corresponds to a program like that:

x: if <some condition> goto z
y: do { <instruction>
z: }while(<cond condition}
w: end

Notice how there is no way to jump to $z$ without a goto, this is the point of reducibility and it corresponds to well-structured code without goto.

Concerning the back edges, if you take the counter-example for above, notice that there are two different ways to explore this tree in a DFS:

• from $x$, explore $z$ then $y$ and $w$: in this case the edge $z\rightarrow y$ is part of the spanning tree built by the DFS. But $z$ does not dominate $y$ because the path $x\rightarrow y$ does not go through $z$.
• from $x$, explore $y$ then $z$ then $w$: in this case the edge $y\rightarrow z$ is part of the spanning tree built by the DFS. But $y$ does not dominate $z$ because the path $x\rightarrow z$ does not go through $y$.

Maybe the source of your confusion is that domination is related to the initial vertex $x$, and not to the DFS. Recall that a vertex $y$ dominates a vertex $z$ if every path from the initial vertex to $z$ goes through $y$.

• I'm confused because of when he says A flowgraph is reducible when it does not have a strongly connected subgraph with two (or more) entries Isn't a directed cycle a strongly connected subgraph with more than 2 entries? – Hao S Feb 18 '18 at 17:18
• I explained that in my answer: an entry is a node of the SCC which has an edge coming from outside the SCC. – Amaury Pouly Feb 18 '18 at 23:22