Enumeration in Incremental FPT-Time
share
In this paper, we study the relationship of parametrised enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce a hierarchy of enumeration complexity classes for incremental fpt-time and relate it to the class DelayFPT. Furthermore, we define several parametrised function classes and, in particular, introduce the parametrised counterpart of the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, TFNP, known from Megiddo and Papadimitriou (TCS 1991). We show that TF(para-NP) collapsing to F(FPT) is equivalent to OutputFPT coinciding with IncFPT. This result is in turn connected to a collapse in the classical function setting and eventually to the collapse of IncP and OutputP which proves the first direct connection of classical to parametrised enumeration.
READ FULL TEXT