Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KERNELIZATION:
Reports tagged with kernelization:
TR04-027 | 20th February 2004
Henning Fernau

#### Parametric Duality: Kernel Sizes and Algorithmics

We derive the first lower bound results on kernel sizes of parameterized problems. The same idea also allows us to sometimes "de-parameterize"
parameterized algorithms.

more >>>

TR07-096 | 8th October 2007
Lance Fortnow, Rahul Santhanam

#### Infeasibility of Instance Compression and Succinct PCPs for NP

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there
is a polynomial-time computable function $f$ and a set $A$ such that
for each instance ... more >>>

TR07-137 | 6th November 2007
Yijia Chen, Jörg Flum, Moritz Müller

#### Lower Bounds for Kernelizations

Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>>

TR10-038 | 10th March 2010
Dieter van Melkebeek, Holger Dell

#### Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Revisions: 1

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>

TR12-112 | 7th September 2012
Andrew Drucker

Revisions: 3

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression ... more >>> TR14-075 | 16th May 2014 Holger Dell #### A simple proof that AND-compression of NP-complete problems is hard Revisions: 3 Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result. An AND-compression is ... more >>> TR19-146 | 31st October 2019 Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau #### Dynamic Kernels for Hitting Sets and Set Packing Computing kernels for the hitting set problem (the problem of finding a size-$k$set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with$m$hyperedges, each of size at most~$d$, the best algorithms can compute kernels of size$O(k^d)\$ in ... more >>>

ISSN 1433-8092 | Imprint