TY - GEN
T1 - On the Hardness of Compressing Weights.
AU - Jansen, Bart M. P.
AU - Roy, Shivesh Kumar
AU - Wlodarczyk, Michal
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2021/8/1
Y1 - 2021/8/1
N2 - We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edge-weighted 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 O(n3ϵ) 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 2O(n), which yields a randomized kernel of O(n3) bits. We generalize these results to the weighted d-Uniform 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 node-weighted 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 inclusion-minimal solutions, then weights as large as 2Ω(n) are necessary.
AB - We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the instance size. Our main focus is the weighted Clique problem, where we are given an edge-weighted 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 O(n3ϵ) 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 2O(n), which yields a randomized kernel of O(n3) bits. We generalize these results to the weighted d-Uniform 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 node-weighted 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 inclusion-minimal solutions, then weights as large as 2Ω(n) are necessary.
KW - Compression
KW - Constraint satisfaction problems
KW - Edge-weighted clique
KW - Kernelization
UR - http://www.scopus.com/inward/record.url?scp=85115368639&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2021.64
DO - 10.4230/LIPIcs.MFCS.2021.64
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 64:1-64:21
BT - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
A2 - Bonchi, Filippo
A2 - Puglisi, Simon J.
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021
Y2 - 23 August 2021 through 27 August 2021
ER -