3
$\begingroup$

Is Max 3-SAT a W[1] hard problem, parmeterized by some parmeterize? I can't find the relevant literature.

I accept any parameterization.

$\endgroup$
3
  • $\begingroup$ Is the question whether there exists any parameter at all that makes MaxSat W[1]-hard? $\endgroup$
    – Pål GD
    Nov 5 '21 at 17:36
  • $\begingroup$ Like the parameter 1? $\endgroup$
    – Pål GD
    Nov 5 '21 at 17:50
  • $\begingroup$ Please clarify what you mean. Do you accept any parameterization? Or do you mean that max-parameter? $\endgroup$
    – Pål GD
    Dec 7 '21 at 22:50
1
$\begingroup$

The W hierarchy consists of classes of decision problems. The decision versions of MAX-SAT problems are just slightly disguised SAT problems. For example, to transform the decision problem "is there a variable assignment that satisfies k clauses?", add a unique variable to each CNF clause, then add a constraint that demands that at least k of the unique variables be set false. (All this can be done in polynomial time.) If the resulting SAT instance is satisfiable, the answer to the MAX-SAT problem is yes, otherwise the answer is no.

Since SAT Karp-reduces to CLIQUE and CLIQUE is W[1]-hard, SAT must be as well, and therefore so is the decision version of MAX-SAT.

$\endgroup$
2
  • $\begingroup$ SAT Karp-reduces to CLIQUE cannot show that SAT must be W[1] hard. If clique can reduce to SAT, it is right. Is my understanding correct? $\endgroup$
    – zhukui bai
    Nov 7 '21 at 3:28
  • $\begingroup$ So MAX SAT is W-hard for what parameter? Also, as an example, vertex cover reduces to clique, yet VC is not W-hard (for the natural parameter). $\endgroup$
    – Juho
    Nov 7 '21 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.