Scholarlink

<p>In this paper, we investigate the approximation and parameterized complexities of MAXNAESAT variants. We begin by presenting a simple yet rigorous proof establishing the <b>APX-completeness</b> of the MAXNAE2SAT problem. Notably, <b>APX-completeness</b> holds even when the repetition factor of each variable is bounded by 3, i.e., each variable appears in at most three clauses in the MAXNAE2SAT instance. Our <b>APX-completeness</b> proof is a strict reduction that directly establishes a new inapproximability bound for the MAXNAE2SAT problem. The decision version of MAXNAE2SAT remains <b>NP-complete</b> when the repetition factor of each variable is bounded by 3, mirroring the <b>NP-completeness</b> of MAXCUT in cubic graphs. We further establish a tight computational dichotomy by proving that the MAXNAE2SAT problem is solvable in linear time when the repetition factor of each variable is bounded by 2. One of our principal contributions is the design and analysis of a <b>fixed-parameter tractable</b> algorithm for MAXNAE2SAT instances with repetition factor three, complemented by an exact exponential-time algorithm for the same setting. Finally, we describe a collection of complexity-preserving reductions among MAXSAT variants, thereby clarifying the structural relationships that unify these problems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An Algorithmic Analysis of MAXNAESAT Variants

  • 期刊论文

  • 发表日期：

    2026年5月13日

查看全文
  • Sangram K. Jena,
  • K. Subramani

摘要

In this paper, we investigate the approximation and parameterized complexities of MAXNAESAT variants. We begin by presenting a simple yet rigorous proof establishing the APX-completeness of the MAXNAE2SAT problem. Notably, APX-completeness holds even when the repetition factor of each variable is bounded by 3, i.e., each variable appears in at most three clauses in the MAXNAE2SAT instance. Our APX-completeness proof is a strict reduction that directly establishes a new inapproximability bound for the MAXNAE2SAT problem. The decision version of MAXNAE2SAT remains NP-complete when the repetition factor of each variable is bounded by 3, mirroring the NP-completeness of MAXCUT in cubic graphs. We further establish a tight computational dichotomy by proving that the MAXNAE2SAT problem is solvable in linear time when the repetition factor of each variable is bounded by 2. One of our principal contributions is the design and analysis of a fixed-parameter tractable algorithm for MAXNAE2SAT instances with repetition factor three, complemented by an exact exponential-time algorithm for the same setting. Finally, we describe a collection of complexity-preserving reductions among MAXSAT variants, thereby clarifying the structural relationships that unify these problems.