2
$\begingroup$

Define $$\text{SQE}=\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\}$$ and $$\text{VC}=\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\}$$

I am trying to prove that SQE is NP-hard via the reduction $VC\leq_P SQE$.

My attempt:

Given a $G=(V,E)$, we want to construct some system of quadratic equations $S$, such that $G\in VC$ if and only if $S$ has real solutions.

For each $u\in V$ introduce the variable $x_u$. We want $x_u=1$ represent vertex $u$ being in the vertex cover and $x_u=0$ to represent it is not. How can we capture, using a quadratic equation, the fact that in a vertex-cover every edge is covered?

For each edge $\{u,v\}\in E$ we introduce the following inequality. $$x_u + x_v \geq 1$$ However, we are not allowed inequalities. With some thought I came up with the following to replace the inequality. $$x_u+x_v-x_ux_v=1$$ This is equal to $1$ if and only if either $u$ or $v$ or both are in the vertex-cover.

However, the domain for an $x_u$ is the reals, but we want to operate in $\{0,1\}$, so that each vertex is either chosen or not. Therefore, we can introduce for each $v\in V$ the following equation $$x_v^2 = x_v$$ which has solutions $0$ or $1$ only.

Now we just need to limit the number of vertices in the vertex-cover to $\leq k$. Using an inequality this is written $\sum_{u\in V}{x_u}\leq k$. I now need some quadratic function $f(x_{u_1}, x_{u_2}, ..., x_{u_n}) = c$ if and only if $\sum_{u\in V}{x_u}\leq k$. But I can't figure out what it should look like.

$\endgroup$

1 Answer 1

2
$\begingroup$

Add $k$ Boolean variables $z_1,\ldots,z_k$ and the constraint $\sum_{u \in V} x_u + \sum_{i=1}^k z_i = k$.

(Optimization: add $\ell = \lceil \log_2 k \rceil$ Boolean variables $w_1,\ldots,w_\ell$ and the constraint $\sum_{u \in V} x_u + \sum_{j=1}^\ell 2^{j-1} w_j = k$.)

$\endgroup$
1
  • $\begingroup$ Ohhh. I am a dummy haha. Thank you. $\endgroup$
    – Tom Finet
    Apr 3, 2022 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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