Parameterized Complexity Classes under Logical Reductions

摘要

The parameterized complexity classes of the W-hierarchy are usually defined as the problems reducible to certain natural complete problems by means of fixed-parameter tractable (fpt) reductions. We investigate whether the classes can be characterised by means of weaker, logical reductions. We show that each class W[t] has complete problems under slicewise bounded-variable first-order reductions. These are a natural weakening of slicewise bounded-variable LFP reductions which, by a result of Flum and Grohe, are known to be equivalent to fpt=reductions. If we relax the restriction on having a bounded number of variables, we obtain reductions that are too strong and, on the other hand, if we consider slicewise quantifier-free first-order reductions, they are considerably weaker. These last two results are established by considering the characterisation of W[t] as the closure of a class of Fagin-definability problems under ./pf-reductions. We show that replacing these by slicewise first-order reductions yields a hierarchy that collapses, while allowing only quantifier-free first-order reductions yields a hierarchy that is provably strict.