Magnus Wahlstrom

  1. Preprocessing of Min Ones Problems: A Dichotomy.

    Authors: Stefan Kratsch, Magnus Wahlstrom
    Subjects: Computational Complexity
    Abstract

    A parameterized problem consists of a classical problem and an additional
    component, the so-called parameter. This point of view allows a formal
    definition of preprocessing: Given a parameterized instance (I,k), a polynomial
    kernelization computes an equivalent instance (I',k') of size and parameter
    bounded by a polynomial in k. We give a complete classification of Min Ones
    Constraint Satisfaction problems, i.e., Min Ones SAT(\Gamma), with respect to
    admitting or not admitting a polynomial kernelization (unless NP \subseteq
    coNP/poly). For this we introduce the notion of mergeability.

Syndicate content