This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes:
Observe that the number of minimal, and even minimum solutions, can be
exponential in the size of the graph; Fig. 1 gives an example.
Therefore, the total running time of any enumeration algorithm cannot
be expected to be polynomial in the size of the graph.
The paper goes onto explain the concept of polynomial delay,
However, certain enumeration algorithms for other combinatorial
problems work with polynomial delay, i.e., the algorithm performs at
most a polynomial number of steps before the first and between
What's polynomial isn't the entire runtime of the algorithm, its the time between successive outputs. Since the algorithm can output an exponential number of items, the total run time can quite easily be exponential.
When it comes to memory, the paper states:
Note that memory requirements are polynomial for graphs with a
polynomial number of MFVS, but potentially exponential for the general
Memory goes exponential if we have an exponential number of outputs. But in that case, there is an exponential amount of time passing to fill up that amount of memory as well.
Put another way, memory is exponential because we are measuring memory usage over the entire enumeration process. Time is polynomial because we are only measuring time between two outputs.