How can an algorithm have exponential space complexity but polynomial time complexity?

Question

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback problems". It is said that it runs in polynomial time but uses exponential space in a dictionary.

insert F_q into Q and into D;
while Q is not empty do
  remove any set F from Q;
  output F;
  for each uG-successor F′ of F do
    if F′ is not contained in D
      insert F′ into D and Q;
    fi
  od
od

How can this be? Does an exponential number of insert operations to the dictionary not inevitably imply exponential time?

Answer 1

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 successive outputs.

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 case.

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.

Answer 2

What they probably mean is that the domain of the dictionary has exponential size. This is not a problem since you can implement the dictionary using a hash table. If the program runs in time $T$ then the hash table would have size $O(T)$ and all operations have expected time $O(1)$.

Note, however, that using a hash table we only get a randomized algorithm; if you want a deterministic algorithm then you might lose some $\log T$ factor in the running time (say using some self-balancing binary tree), but it will remain polynomial.

Answer 3

You're correct that on a Turing machine, any algorithm that uses space $f(n)$ must use time $f(n)$ to move the tape heads far enough to access that space. However, models of computation that allow random access to data held in memory don't necessarily have that property.

Answer 4

Splitting calculations into space and time is one way to describe the behavior of the equation. What this is saying is that the calculations do not need to actually compute over the full size of the data to compute the result. This is maybe reasonable since you only need to locate a single vertex in each cycle.

didn't read the full algorithm but probably it has something to do with

Say you have a clique of size N. That queue could approach N! in size, but you may not actually need to computer over the full N! edges to find the solution