Abstract | ||
---|---|---|
Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceeding some bound. For example, d-Set Matching for integers d ≥ 3 is the problem of finding a matching of size at least k in a given d-uniform hypergraph and has kernels with O(kd) edges. Recently, Bodlaender et al. [ICALP 2008], Fortnow and Santhanam [STOC 2008], Dell and Van Melkebeek [STOC 2010] developed a framework for proving lower bounds on the kernel size for certain problems, under the complexity-theoretic hypothesis that coNP is not contained in NP/poly. Under the same hypothesis, we show lower bounds for the kernelization of d-Set Matching and other packing problems. Our bounds are tight for d-Set Matching: It does not have kernels with O(kd−ε) edges for any ε > 0 unless the hypothesis fails. By reduction, this transfers to a bound of O(kd−1−ε) for the problem of finding k vertex-disjoint cliques of size d in standard graphs. It is natural to ask for tight bounds on the kernel sizes of such graph packing problems. We make first progress in that direction by showing non-trivial kernels with O(k2.5) edges for the problem of finding k vertex-disjoint paths of three edges each. This does not quite match the best lower bound of O(k2−ε) that we can prove. Most of our lower bound proofs follow a general scheme that we discover: To exclude kernels of size O(kd−ε) for a problem in d-uniform hypergraphs, one should reduce from a carefully chosen d-partite problem that is still NP-hard. As an illustration, we apply this scheme to the vertex cover problem, which allows us to replace the number-theoretical construction by Dell and Van Melkebeek [STOC 2010] with shorter elementary arguments. |
Year | DOI | Venue |
---|---|---|
2012 | 10.5555/2095116.2095122 | SODA |
Keywords | Field | DocType |
graph packing problem,van melkebeek,vertex cover problem,packing problem,d-set matching,certain problem,kernel size,d-partite problem,lower bound,size o | Kernel (linear algebra),Kernelization,Integer,Discrete mathematics,Combinatorics,Packing problems,Upper and lower bounds,Hypergraph,Constraint graph,Vertex cover,Mathematics | Conference |
Volume | ISBN | Citations |
abs/1812.03155 | 978-1-61197-251-1 | 38 |
PageRank | References | Authors |
1.25 | 23 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Holger Dell | 1 | 220 | 16.74 |
Dániel Marx | 2 | 1952 | 113.07 |