On the Hardness of Compressing Weights
Bart M. P. Jansen Eindhoven University of Technology�Shivesh K. Roy Eindhoven University of Technology�Michał Włodarczyk Eindhoven University of Technology
MFCS 2021�Aug 23-27, 2021, Tallinn (Estonia)
Data reduction with a guarantee for NP-hard problems
2
A kernelization guarantees that instances that are large �with respect to their complexity parameter can be shrunk
Unweighted vs. Weighted problems
3
Weights in kernelization
4
Is this overhead in the kernel size of weighted problems necessary?
?
Exact-Edge-Weight Clique (EEWC)
5
t= 21
Exact-Edge-Weight Clique (EEWC)
6
Our results for Exact-Weighted problems:
7
Problem | Parameter | | Kernel upper bound (Randomized) |
Exact-Edge-Weight Clique (EEWC) | #vertices n | | |
| #vertices n | | |
| #vertices n | ? | |
| #variables n | | |
Subset Sum | #items n | | Matching upper bound is known [Harnik & Naor, SICOMP] |
Tightens result of Etscheid et al. [JCSS] who ruled out standard kernelization assuming ETH
Our results for Weighted Vertex Cover
8
Towards cubic lower bound for EEWC
9
Key lemma
10
Hypothetical Kernel
11
# vertices added
Conclusion
12
THANK YOU!