Главная

Stefan Kratsch

  1. Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem.

    Ср, 07/20/2011 - 15:01 — SomNambul
    Authors: Stefan Kratsch
    Subjects: Data Structures and Algorithms
    Abstract

    Until recently, techniques for obtaining lower bounds for kernelization were
    one of the most sought after tools in the field of parameterized complexity.
    Now, after a strong influx of techniques, we are in the fortunate situation of
    having tools available that are even stronger than what has been required in
    their applications so far. Based on a result of Fortnow and Santhanam (JCSS
    2011), Bodlaender et al.

  2. On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal.

    Ср, 07/20/2011 - 15:01 — SomNambul
    Authors: Stefan Kratsch, Bart M. P. Jansen
    Subjects: Data Structures and Algorithms
    Abstract

    The Odd Cycle Transversal problem (OCT) asks whether a given graph can be
    made bipartite (i.e., 2-colorable) by deleting at most l vertices. We study
    structural parameterizations of OCT with respect to their polynomial
    kernelizability, i.e., whether instances can be efficiently reduced to a size
    polynomial in the chosen parameter. It is a major open problem in parameterized
    complexity whether Odd Cycle Transversal admits a polynomial kernel when
    parameterized by l.

  3. Preprocessing of Min Ones Problems: A Dichotomy.

    Пнд, 10/26/2009 - 14:11 — SomNambul
    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.

Math-arch

RSS-материал