Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}

Question

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) notin$ VC $implies (a,k)notin 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?

Watercrystal · Accepted Answer

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 :)

Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}

One Answer

Add your own answers!

Ask a Question