Details

Autor(en) / Beteiligte

• Jansen, Bart M. P.
• Włodarczyk, Michał

Titel

Optimal Polynomial-Time Compression for Boolean Max CSP

Ist Teil von

• ACM transactions on computation theory, 2024-03, Vol.16 (1), p.1-20, Article 4

Ort / Verlag

New York, NY: ACM

Erscheinungsjahr

2024

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 (nd log n) bits in polynomial time, (2)Max CSPΓ does not admit such a compression to (nd-ε) 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 CSPs is as hard as breaching this barrier for Max d-SAT for some d.