# vertex cover reduction to subset sum

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

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?

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}$$

• Nice idea to use base 4! Dec 8, 2019 at 12:06