Problem $4.$ NP$-$hardness $(47$ Points$)$

To prove NP$-$hardness for each problem below you must first describe a polynomial time

reduction from one of the problems above, then briefly describe why the reduction is correct.

$($Note each problem is in fact NP$-$Complete though you only need to prove NP$-$hardness.$)$

$($a$)(10$ points$)$

Problem: TTF$3$SAT

Instance: A boolean formula $f$ in $3CNF$ form with $n$ variables and $m$

clauses.

Question: Is there a variable assignment such that, for any $i,$ clause $i$

is False if $i$ is a multiple of $3,$ and otherwise clause $i$ is True.

Prove that TTF$3$SAT is NP$-$hard.

$($b$)(11$ points$)$

Problem: Bounded Degree Spanning Tree

Instance: An undirected graph $G=(V,E),$ and an integer $k.$

Question: Is there a spanning tree of $G$ such that the degree of every

vertex, as measured with respect to the spanning tree, is $k?$

Prove that Bounded Degree Spanning Tree is NP$-$hard.

$($c$)(13$ points$)$

Problem: KNAPSACK

Instance: An array of values $V[1$dotsn$],$ an array of sizes $S[1$dotsn$],$ a

bag size $B,$ and a number $k.$

Question: Is there a subset of indices I such that ${\displaystyle \underset{\text{i}\text{i}\text{n}\text{I}}{\overset{?}{}}}V[i]k$ and

${\displaystyle \underset{\text{i}\text{i}\text{n}\text{I}}{\overset{?}{}}}S[i]B.$

Prove that Knapsack is NP$-$hard.

$($d$)(13$ points$)$

Problem: BI$-$Cover

Instance: An undirected, bipartite graph $G=(V,E),$ and an integer $k.$

Let $A,B$ denote the bipartition are independent and $AB=V.$

Question: Is there a subset of at most $k$ vertices UsubeA such that every

vertex of $B$ is adjacent to a vertex of $U?$

Prove that Bi$-$Cover is NP$-$hard.