PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving MAX-r-SAT Above a Tight Lower Bound

Noga Alon, Gregory Gutin, Eun Jung Kim, Stefan Szeider, Anders Yeo

arXiv:0907.4573v4cs.DScs.CC

TL;DR

Max-r-Sat above its tight lower bound had an open parameterized-complexity question. The paper uses algebraic data reduction and probabilistic arguments to obtain fixed-parameter and kernel results. It also gives a specialized Max-2-Sat bound and outlines extensions to Boolean constraint-satisfaction problems.

  • Problem

    The parameterized complexity of deciding whether Max-r-Sat exceeds its tight lower bound, (1 − 2^-r)m, was an open question.

    Source: §1 · p. 3

  • Method

    An algebraic data-reduction procedure combines polynomial representation, probabilistic reasoning, and harmonic analysis to reduce instances to O(k^2) variables.

    Source: §1 · p. 2

  • Results

    For every fixed r, Max-r-Sat above its tight lower bound is decidable in O(m) + 2^O(k^2) time and has a polynomial-size kernel; the paper also gives a Max-2-Sat bound and kernel result.

    Source: §1 · p. 2, §4.3 · p. 6

  • Takeaways & Limitations

    The authors outline extending the fixed-parameter and polynomial-kernel results to more general Boolean constraint-satisfaction problems; they describe the results as mainly theoretical.

    Source: §6 · p. 12, §7 · p. 13

    The results are mainly of theoretical interest; the Max-2-Sat kernel may be practically relevant for instances whose maximum satisfied-clause count is close to 3m/4.

    Source: §7 · p. 13

Abstract

from arXiv · show

We present an exact algorithm that decides, for every fixed $r \geq 2$ in time $O(m) + 2^{O(k^2)}$ whether a given multiset of $m$ clauses of size $r$ admits a truth assignment that satisfies at least $((2^r-1)m+k)/2^r$ clauses. Thus \textsc{Max-$r$-Sat} is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound $(1-2^{-r})m$. This solves an open problem of Mahajan et al. (J. Comput. System Sci., 75, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with $O(k^2)$ variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size $O(k^2)$, then there is a truth assignment satisfying the required number of clauses. We introduce a new notion of bikernelization from a parameterized problem to another one and apply it to prove that the above-mentioned parameterized \textsc{Max-$r$-Sat} admits a polynomial-size kernel. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of \textsc{Max-2-Sat} with $m$ clauses has at least $3k$ variables after application of certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least $(3m+k)/4$ clauses. We also outline how the fixed-parameter tractability and polynomial-size kernel results on \textsc{Max-$r$-Sat} can be extended to more general families of Boolean Constraint Satisfaction Problems.

1 Introduction

The paper resolves the open parameterized-complexity question for Max-r-Sat above its tight lower bound. It presents an algebraic reduction, kernel results, a specialized Max-2-Sat result, and an outline for extending the approach to Boolean constraint-satisfaction problems.

1 Introduction

  • For every fixed r, Max-r-Sat above its tight lower bound is decidable in O(m) + 2^O(k^2) time, answering an open question of Mahajan, Raman and Sikdar.The target is at least ((2^r − 1)m + k)/2^r satisfied clauses.Source: §1 · pp. 2–3
  • An algebraic data-reduction procedure produces an equivalent problem with O(k^2) variables, using probabilistic reasoning and harmonic analysis.If the polynomial cannot be reduced to that size, the argument yields an assignment meeting the required clause threshold.Source: §1 · p. 2
  • The approach also establishes a polynomial-size kernel for Max-r-Sat, using bikernelization and a general lemma.The authors also give a more efficient direct argument.Source: §1 · p. 2
  • For Max-2-Sat, at least 3k variables remaining after a polynomial-time reduction rule guarantee an assignment satisfying at least (3m + k)/4 clauses.The argument combines probabilistic reasoning with graph matching and signed-graph tools.Source: §1 · p. 2
  • The fixed-parameter and polynomial-kernel results are outlined for extension to more general families of Boolean constraint-satisfaction problems.Source: §1 · p. 2
  • Mahajan et al. list exact Max-r-Sat, with m clauses each containing exactly r different literals, parameterized by satisfied clauses above the tight lower bound (1 - 2^-r)m, among problems whose parameterized complexity is open.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the clause and assignment conventions, introduce the above-tight-lower-bound problems, and recall parameterized complexity and the probabilistic method.

2 Preliminaries

  • An r-CNF formula is a finite multiset of clauses, each containing exactly r different literals; assignments use values −1 and 1.The paper denotes the number of satisfied clauses by sat(τ, F) and the maximum over assignments by sat(F).Source: §2 · p. 3
  • A parameterized problem is fixed-parameter tractable when it can be decided in |x|^O(1) · f(k) time, and kernelization reduces instances in polynomial time to equivalent bounded-size instances.The section also notes that a decidable parameterized problem is fixed-parameter tractable exactly when it has a kernelization.Source: §2 · p. 3
  • Max-r-Sattlb takes an instance (F, k), where F is a multiset of m clauses of size r and k is a nonnegative integer; its parameter is k.Mahajan et al. use a slightly different formulation, asking for at least (1 − 2^-r)m + k satisfied clauses; since r is fixed, this change does not affect complexity.Source: §2 · p. 3
  • Max-r-Lin2tlb asks whether weighted equations over F2, each with at most r variables, can be satisfied with total weight at least (W + k)/2.A random assignment satisfies expected weight W/2, which is tight; prior work gives a kernel with O(k^2) equations and variables.Source: §2 · p. 4
  • The probabilistic method uses linearity of expectation and averaging: positive probability of an event guarantees an assignment realizing it.Source: §2 · p. 4

3 Bikernelization

Bikernelization generalizes kernelization by reducing one parameterized problem to another. The section connects such reductions to fixed-parameter tractability and polynomial-size kernels.

3 Bikernelization

  • A bikernelization maps an instance of one parameterized problem to an equivalent instance of another, with parameter and instance size bounded by functions of the original parameter.Ordinary kernelization is the special case where the source and target problems are the same.Source: §3 · p. 4
  • A decidable parameterized problem is fixed-parameter tractable exactly when it admits a bikernelization to a decidable parameterized problem.The target instance can be decided in time depending only on its bounded parameter.Source: §3 · p. 4
  • For NP-complete L and L′ in NP, a polynomial-size bikernel from L to L′ implies a polynomial-size kernel for L.The proof reduces the bikernel instance back to L in polynomial time.Source: §3 · pp. 4–5

4 MAX-r-SAT

The section represents the satisfaction excess as a polynomial and uses probabilistic and harmonic-analysis arguments to reduce the problem. It establishes fixed-parameter tractability and quadratic-size kernels for Max-r-Sat above its tight lower bound.

4.1 An Algebraic Representation

  • An algebraic representation maps each assignment to a polynomial value equal to 2^r times its satisfied clauses above the tight lower bound.After simplification, the polynomial is a sum of nonzero-coefficient terms, each involving at most r variables.Source: §4.1 · p. 5

4.2 The Properties of X

  • For independent uniform ±1 variables, the polynomial has mean zero and its fourth moment is at most 9^r times the square of its second moment.This moment bound is used in the probabilistic argument about the polynomial.Source: §4.2 · pp. 5–6

4.3 The Main Result for General r

  • For every fixed r, Max-r-Sat above its tight lower bound is solvable in O(m)+2^O(k^2) time and has O(k^2)-size kernels.The polynomial can be simplified in O(m) time; in the reduced case it has O(k^2) terms and variables, and its maximum can be found in 2^O(k^2) time.Source: §4.3 · pp. 6–7
  • If the simplified polynomial has more than 4·3^2r k^2 nonzero terms, the instance is a yes-instance; otherwise, its size is O(k^2).In the reduced case, the polynomial has O(k^2) variables and its maximum can be found in 2^O(k^2) time.Source: §4.3 · pp. 6–7
  • The simplified polynomial also yields an O(k^2)-size bikernel from Max-r-Sat to Max-r-Lin2.Each nonzero polynomial term is converted into a weighted linear equation over F2.Source: §4.3 · p. 7
  • Replacing each linear equation by 2^(r−1) clauses preserves the number of unsatisfied constraints, yielding an O(k^2)-size kernel for Max-r-Sat.The conversion applies to equations with at most r variables, and r is fixed.Source: §4.3 · p. 7
  • The algorithm can efficiently find an assignment meeting an above-average satisfaction target using variables that are 4r-wise independent.The proof requires only 4r-wise independence, for which polynomial-size sample spaces are known.Source: §4.3 · p. 7

5 MAX-2-SAT

For Max-2-Sat, the section develops a semicomplete reduction and a graph-based kernelization, proving that sufficiently many significant variables guarantee the target satisfaction bound. It also gives a polynomial-time kernel with at most 3k−1 variables.

5.1 The Semicomplete Data Reduction

  • Semicomplete reduction repeatedly deletes semicomplete subsets; every assignment satisfies exactly 2^r−1 clauses in any such subset.Semicomplete formulas have 2^r clauses, and each pair of distinct clauses has a conflict.Source: §5.1 · p. 8

5.2 Kernelization

  • For formulas without semicomplete subsets, more than 3k−2 significant variables guarantee sat(F) ≥ (3m + k)/4, yielding a Max-2-Sat kernel with at most 3k−1 variables.The reduction procedure first removes semicomplete subsets; the kernel corollary applies after that reduction.Source: §5.2 · pp. 9, 12
  • Induced stars allow switching to achieve weight at least their number of leaves; matching and the Tutte-Berge formula then bound graph size in a no-instance.The weighted auxiliary graph represents variables, and the reduction targets a subset whose switched weight reaches k.Source: §5.2 · pp. 10–12
  • When the variable threshold is not met, insignificant variables can be consolidated, and instances with more than 8k clauses can be solved optimally in polynomial time.The resulting kernel has at most 3k−1 variables and at most 8k clauses.Source: §5.2 · p. 12

6 Extension to Boolean Constraint Satisfaction Problems

The paper extends above-baseline parameterization from Max-r-Sat to Boolean r-CSPs. It proves fixed-parameter tractability and a polynomial-size bikernel, with polynomial kernels for NP-complete cases.

6 Extension to Boolean Constraint Satisfaction Problems

  • The parameter is the number of satisfied functions above their expected value, which is a tight lower bound when the function family is closed under variable complementation.The formulation includes Max-r-Sat as a special case.Source: §6 · p. 13
  • The proof represents each function by a zero-mean random variable and sums these terms into a degree-at-most-r polynomial whose value encodes the satisfaction surplus.The sum evaluates to 2^r(s−a), where s is the number satisfied and a is its average.Source: §6 · p. 13
  • For Boolean r-CSPs, the problem is fixed-parameter tractable and has a polynomial-size bikernel to Max-r-Lin2tlb of size O(k^2); NP-complete cases have polynomial-size kernels.The results apply to fixed r, with the kernel conclusion stated for NP-complete CSPs.Source: §6 · p. 13

7 Discussions

The authors characterize the results as mainly theoretical, while noting a possible practical niche for the Max-2-Sat kernelization. They also report a later kernel result using a different proof approach.

7 Discussions

  • The Max-2-Sat kernelization may be practically relevant for instance families whose maximum number of satisfied clauses is close to 3m/4.The paper characterizes its results overall as mainly theoretical.Source: §7 · p. 13
  • Crowston et al. later proved an O(k log k)-variable kernel for Max-2-Sattlb, using linear algebra rather than probabilistic tools.Source: §7 · p. 13
Loading 0907.4573v4…