5
$\begingroup$

Subset sum

  • Input: A multi set $S$ of numbers and a natural number $t$
  • Question: Does $S$ contain a subset $A$ such that $\sum_{x \in A} x = t$? (e.g., $\{1,1,2,3,4,5\}$, by multiset it means duplicates are allowed)

Vertex cover

  • Input: An undirected graph $G$ and a number $k$.
  • Question: Does $G$ have a vertex cover of size $k$?

Show: vertex cover $\leq_P$ subset sum


My work so far: I need to somehow transform $(G, k) \to (S, t)$

enter image description here

Above is a example graph $G$ that I constructed. It's vertex covers are $\{v_1, v_3\}$ so the size of the vertex cover is $2$, thus $k = 2$.

This is basically $S$

\begin{array}{|c|c|c|c|c|} \hline & e_1 & e_2 & e_3 & e_4 \\ \hline v_1 & 1& 0& 0& 1\\ \hline v_2 & 1& 1& 0& 0\\ \hline v_3 & 0& 1& 1& 0\\ \hline v_4 & 0& 0& 1&1\\ \hline \end{array}

if $e_i$ and $v_j$ is incident I put $1$; otherwise $0$

Now what I need is a target $t$ to satisfy this.

The matrix above can be written in a set to be $S = \{1001, 1100, 0110, 0011\}$ if I were to add up all these values probably in base 2 since its binary, it would give me a value but I think I need a consistent value $t$, so this wont work. I'm also unsure how to integrate the $k = 2$ into this either.

Could someone help me construct this?

$\endgroup$
1
$\begingroup$

For simplicity write all the numbers in base $4$. Fix an arbitrary ordering of the edges of the graph $G$ and let $e_i$ be the $i$-th edge ($i= 1, \dots, |E(G)|$).

For each vertex $v \in V(G)$ define an integer $n_v$ of $|E(G)| + 1$ digits as follows:

  • the $i$-th least significant digit of $n_v$ is $1$ if $e_i$ is incident to $v$ and $0$ otherwise;
  • the most significant digit of $n_v$ is $1$.

For each edge $e_i \in E(G)$ let $m_{e_i} = 4^{i-1}$ (i.e., the $i$-th least significant digit of $m_e$ is $1$ and all the other digits are $0$).

The instance of subset sum is obtained by choosing $S = \{ n_v : v \in V(G) \} \cup \{m_e : e \in E(G) \}$ and $t = k 4^{|E(G)|} + 2\sum_{i=0}^{|E(G)|-1} 4^i$. In other words, the most significant digits of $t$ encode the number $k$ in base $4$, while the $|E(G)|$ least significant digits of $t$ are all equal to $2$.


If there is a vertex cover $V' \subseteq V(G)$ of $G$ of size $k$, let $E'$ be the set of edges $(u,v) \in E(G)$ such that exactly one of $u$ and $v$ is in $V'$. Then, $A = \{ n_v : v \in V' \} \cup \{ m_e : e \in E' \}$ is a subset of $S$ that sums to $t$. Indeed: $$ \sum_{x \in A} x = \sum_{v \in V'} n_v + \sum_{e \in E'} m_v = k 4^{|E(G)|} + 2 \sum_{e_i \in E \setminus E'} 4^{i-1} + 2 \sum_{e_i \in E'} 4^{i-1} = k 4^{|E(G)|} + 2 \sum_{e_i \in E} 4^{i-1} = t. $$

If there is a subset $A$ of $S$ that sums to $t$, then $A$ contains exactly $k$ numbers from $\{ n_v : v \in V(G) \}$ (as otherwise the most significant digits of $\sum_{x \in A} x$ would not match those of $t$). Moreover, $V' = \{v_i : n_i \in A \}$ is a vertex cover for $G$.

To see this, pick any $e_i = (u,v) \in E(G)$ and notice the $i$-th least significant digit of $t$ is $2$. Since, for $j=1,\dots, |E(G)|$, there are exactly $3$ numbers in $S$ whose $j$-th least significant digit is non-zero (namely $n_{u'}$, $n_{v'}$, and $m_{e_j}$, where $e_j = (u', v')$), we have that in the summation $\sum_{x \in A} x$ no carry occurs among the $|E(G)|$ least significant digits. We conclude that $A$ contains exactly two numbers from $\{n_u, n_v, m_e\}$, implying that $u \in V'$ or $v \in V'$ (possibly both).


In your example graph, for $k=3$ you get the following (bold rows denote the elements of $A$ when $V'=\{v_1, v_3, v_4\}$): $$ \begin{array}{|c|c|c|c|c|} \hline & & e_1 & e_2 & e_3 & e_4 \\ \hline \pmb{n_{v_1}} & \pmb{1} & \pmb{1}& \pmb{0}& \pmb{0}& \pmb{1}\\ \hline n_{v_2} & 1 & 1& 1& 0& 0\\ \hline \pmb{n_{v_3}} & \pmb{1} & \pmb{0} & \pmb{1} & \pmb{1} & \pmb{0}\\ \hline \pmb{n_{v_4}} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{1} & \pmb{1}\\ \hline \end{array} $$ $$ \begin{array}{|c|c|c|c|c|} \hline & & e_1 & e_2 & e_3 & e_4 \\ \hline \pmb{m_{e_1}} & \pmb{0} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{0} \\ \hline \pmb{m_{e_2}} & \pmb{0} & \pmb{0}& \pmb{1}& \pmb{0}& \pmb{0}\\ \hline m_{e_3} & 0 & 0& 0& 1& 0\\ \hline m_{e_4} & 0 & 0& 0& 0& 1\\ \hline \end{array} $$

$$ \begin{array}{|c|c|c|c|c|} \hline \phantom{m_{e_4}}& & e_1 & e_2 & e_3 & e_4 \\ \hline t & 3 & 2& 2& 2& 2\\ \hline \end{array} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice idea to use base 4! $\endgroup$ – j_random_hacker Dec 8 '19 at 12:06

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.