Jansen, Bart M. P. ;
Roy, Shivesh K. ;
Włodarczyk, Michał
On the Hardness of Compressing Weights
Abstract
We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomialtime preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edgeweighted graph and the goal is to detect a clique of total weight equal to a prescribed value. We show that the weighted variant, parameterized by the number of vertices n, is significantly harder than the unweighted problem by presenting an 𝒪(n^{3  ε}) lower bound on the size of the kernel, under the assumption that NP ̸ ⊆ coNP/poly. This lower bound is essentially tight: we show that we can reduce the problem to the case with weights bounded by 2^𝒪(n), which yields a randomized kernel of 𝒪(n³) bits.
We generalize these results to the weighted dUniform Hyperclique problem, Subset Sum, and weighted variants of Boolean Constraint Satisfaction Problems (CSPs). We also study weighted minimization problems and show that weight compression is easier when we only want to {preserve the collection of} optimal solutions. Namely, we show that for nodeweighted Vertex Cover on bipartite graphs it is possible to maintain the set of optimal solutions using integer weights from the range [1, n], but if we want to maintain the ordering of the weights of all inclusionminimal solutions, then weights as large as 2^Ω(n) are necessary.
BibTeX  Entry
@InProceedings{jansen_et_al:LIPIcs.MFCS.2021.64,
author = {Jansen, Bart M. P. and Roy, Shivesh K. and W{\l}odarczyk, Micha{\l}},
title = {{On the Hardness of Compressing Weights}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {64:164:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14504},
URN = {urn:nbn:de:0030drops145049},
doi = {10.4230/LIPIcs.MFCS.2021.64},
annote = {Keywords: kernelization, compression, edgeweighted clique, constraint satisfaction problems}
}
18.08.2021
Keywords: 

kernelization, compression, edgeweighted clique, constraint satisfaction problems 
Seminar: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Issue date: 

2021 
Date of publication: 

18.08.2021 