Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Kernelization Lower Bounds for Finding Constant-Size Subgraphs   Kernelization is an important tool in parameterized algorithmics. Given an
input instance accompanied by a parameter, the goal is to compute in polynomial
time an equivalent instance of the same problem such that the size of the
reduced instance only depends on the parameter and not on the size of the
original instance. In this paper, we provide a first conceptual study on limits
of kernelization for several polynomial-time solvable problems. For instance,
we consider the problem of finding a triangle with negative sum of edge weights
parameterized by the maximum degree of the input graph. We prove that a
linear-time computable strict kernel of truly subcubic size for this problem
violates the popular APSP-conjecture.

0
The categories of this paper are: hep-ph
25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
15
The categories of this paper are: nucl-ex
11
The categories of this paper are: hep-lat
14
The categories of this paper are: math-ph
23
The categories of this paper are: solv-int
34
The categories of this paper are: chem-ph
29
The categories of this paper are: funct-an
7
The categories of this paper are: hep-th
6
The categories of this paper are: astro-ph
10
The categories of this paper are: q-bio
21
The categories of this paper are: adap-org
19
The categories of this paper are: eess
26
The categories of this paper are: bayes-an
22
The categories of this paper are: chao-dyn