Optimal Polynomial-Time Compression for Boolean Max CSP
ACM Transactions on Computation Theory · 31.03.2024 · 16 (1) · 1-20
DOI: 10.1145/3624704 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, online erschienen am 12.03.2024. Verfasst von Bart M. P. Jansen und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council erc (ERC) under the European Union’s Horizon 2020 research and innovation programme, Foundation for Polish Science.
Abstract (Originalsprache)
In the Boolean maximum constraint satisfaction problem— Max CSPΓ —one is given a collection of weighted applications of constraints from a finite constraint language Γ, over a common set of variables, and the goal is to assign Boolean values to the variables so that the total weight of satisfied constraints is maximized. There exists a concise dichotomy theorem providing a criterion on Γ for the problem to be polynomial-time solvable and stating that otherwise, it becomes NP-hard. We study the NP-hard cases through the lens of kernelization and provide a complete characterization of Max CSPΓ with respect to the optimal compression size. Namely, we prove that Max CSPΓ parameterized by the number of variables n is either polynomial-time solvable, or there exists an integer d ≥ 2 depending on Γ, such that: (1) An instance of Max CSPΓ can be compressed into an equivalent instance with 𝒪( n d log n ) bits in polynomial time, (2) Max CSPΓ does not admit such a compression to 𝒪( n d-ε ) bits unless NP ⊆ co-NP / poly. Our reductions are based on interpreting constraints as multilinear polynomials combined with the framework of “constraint implementations”, formerly used in the context of APX-hardness. As another application of our reductions, we reveal tight connections between optimal running times for solving Max CSPΓ . More precisely, we show that obtaining a running time of the form 𝒪(2 (1-ε) n ) for particular classes of Max CSP s is as hard as breaching this barrier for Max d -SAT for some d .
Förderung
- European Research Council erc (ERC) under the European Union’s Horizon 2020 research and innovation programme
- Foundation for Polish Science
Zitieren
APA
Jansen, B. M. P., & Włodarczyk, M. (2024). Optimal Polynomial-Time Compression for Boolean Max CSP. ACM Transactions on Computation Theory, 16(1), 1-20. https://doi.org/10.1145/3624704
Vancouver
Jansen BMP, Włodarczyk M. Optimal Polynomial-Time Compression for Boolean Max CSP. ACM Transactions on Computation Theory. 2024;16(1):1-20. doi:10.1145/3624704
BibTeX
@article{Jansen2024,
author = {Jansen, Bart M. P. and Włodarczyk, Michał},
title = {Optimal Polynomial-Time Compression for Boolean Max CSP},
journal = {ACM Transactions on Computation Theory},
year = {2024},
volume = {16},
number = {1},
pages = {1--20},
doi = {10.1145/3624704}
}
EUVIMED