1
$\begingroup$

I have the following question :

\begin{align} L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\ \text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\} \end{align}

I know that $L_2 \in$ NPC.

Show that $L_2 \in$ NP is relatively easy, I'll skip that part.

I try to show that $L_2 \in$ NPC using a reduction from VC $\leq_p L_2$ (VC is vertex cover which we know in its NPC)

I defined the following function $f$ :

$$f(G,k)=(a,k)$$

I thought of something like that for each node $i$ in $G$ will define a literal $x_i$, and make it in 3DNF format, $a=\bigvee(x_i \wedge x_i \wedge x_i)$ where $1 \leq i \leq n$ where $n$ is the number of nodes in $G$. We can define that following $z$ such that $z$ safifies exactly $k$ clauses, just give $'1'$ literal $x_i$ such that the node $i$ is in the VC, and $'0'$ otherwise, so such $z$ exists.

So easy to see that $(G,k) \in$ VC $\implies (a,k) \in L_2$ since we showed explicitly such $z$ that safifies exactly $k$ clauses.

But I'm not sure the other side holds $(G,k) \not\in$ VC $\implies (a,k)\not\in L_2$ we given a graph that doesn't have VC in size $k$ but I think due to my building of a ($a=\bigvee(x_i \wedge x_i \wedge x_i)$) we can find $z$ that safifies exactly $k$ clauses (actually we can find $z$ that safifies $x$ clauses where $1 \leq x \leq n$ where $n$ is number of nodes in $G$.

So my reduction doesn't hold?

$\endgroup$
  • $\begingroup$ Hint: try to reduce from VC with max degree 3, and think of the reduction function $f(G,k)=(a,n-k)$ instead. $\endgroup$ – xskxzr Sep 12 at 10:42
2
$\begingroup$

The reason for why you are having problems is because your solution does not work. In particular, the problem is that your formula does not capture the VC problem statement. More precisely, the formula you build always has assignments satisfying $k$ clauses by just setting $k$ variables to true and the rest to false.

So let $G = (V, E)$ be a graph and $X \subseteq V$ be a VC in $G$. Then for any edge $vw \in E$ we must have $v \in X$ or $w \in X$, giving us 3 mutually exclusive possibilities (by essentially rewriting $v \vee w$ in DNF):

  • $v \in X$ but $w \notin X$,
  • $v \notin X$ but $w \in X$
  • $v \in X$ and $w \in X$

Hence the edge $vw$ is covered by $X$ if and only if the formula $\psi(vw) = (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$ has exactly one satisfied clause (under the assignment corresponding to $X$).

Constructing such a formula for every edge and taking their disjunction, we get the DNF formula $$\psi^\text{VC}(G) = \bigvee_{e \in E} \psi(e) = \bigvee_{vw \in E} (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$$ and any assignment satisfying exactly $|E|$ clauses must be a VC of $G$. Now we need a way to encode the size of the VC into it all, for which we can reuse your idea. Define $$\psi(G) = \psi^\text{VC}(G) \vee \bigvee_{v \in V} v$$ and note that the number of satisfied clauses in the second part is just given by the size of the set of vertices we select, so the total number of satisfied clauses under the assignment corresponding to some VC $X$ in $G$ is $|E| + |X|$.

There is only one problem remaining here. We could get an assignment not corresponding to a VC but including more vertices to satisfy the same number of clauses that a desired VC would. As a remedy, we can repeat the first formula some $|V| + 1$ times such that no matter how many vertices you chose, the total number of satisfied clauses will always be too low.

Hence we obtain the final formula $$\psi^\ast(G) = \bigvee_{i = 1}^{|V| + 1} \psi^\text{VC}(G) \vee \bigvee_{v \in V} v$$ and note that if $G$ has a VC $X$ then the corresponding assignment will satisfy exactly $(|V| + 1) \cdot |E| + |X|$ clauses of $\psi^\ast(G)$. For the reverse direction, let $\alpha$ be some assignment satisfying $(|V| + 1) \cdot |E| + k$ clauses of $\psi^\ast(G)$. Then $\alpha$ must represent a VC in G as otherwise, the number of satisfied clauses in the first part of $\psi^\ast(G)$ is at most $(|V| + 1) \cdot (|E| - 1) = |V| \cdot |E| + |E| - |V| - 1$ and as $\alpha$ can satisfy at most $|V|$ clauses in the second part, the total number of satisfied clauses will be at most $$(|V| + 1) \cdot (|E| - 1) + |V| = |V| \cdot |E| + |E| - 1 < (|V| + 1) \cdot |E|$$ However, this implies that the total number of satisfied clauses in the first part must be exactly $(|V| + 1) \cdot |E|$ and thus exactly $k$ clauses of the second part are satisfied by $\alpha$, so $\alpha$ corresponds to a VC $X_\alpha$ of size $k$ in $G$.

Note that for clarity I did not specify a $3$-DNF formula. However, as all clauses in $\psi^\ast(G)$ are of size at most $2$ you can just add redundant literals to the clauses to blow them up to size $3$ if need be.

I am not sure that this is the best way to do this, but it should work out. I omitted some details for brevity, please feel free to ask for additional clarifications if something is not clear to you :)

| cite | improve this answer | |
$\endgroup$

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.