
Prove that the vertex cover problem (does there exist a subset S of k
vertices in a graph G such that every edge in G is incident upon
at least one vertex in S?) remains NPcomplete even when all the vertices in
the graph are restricted to have even degree.

An instance of the set cover problem consists of a set X of n
elements, a family F of subsets of X, and an integer k.
The question is, do there exist k subsets from F whose union is X?
For example, if and
, there does not exist a solution
for k=2 but there does for k=3 (for example, ).
Prove that set cover is NPcomplete with a reduction from vertex cover.

The baseball card collector problem is as follows.
Given packets , each of which contains a subset of that
year's baseball cards, is it possible to collect all the year's cards
by buying packets?
For example, if the players are and
the packets are
there does not exist a solution
for k=2 but there does for k=3, such as
Prove that the baseball card collector problem is NPhard using a reduction
from vertex cover.

(*)
An Eulerian cycle is a tour that visits every edge in
a graph exactly once.
An Eulerian subgraph is a subset of the edges and vertices of a graph
that has an Eulerian cycle.
Prove that the problem of finding the number of edges in
the largest Eulerian subgraph of a graph is NPhard.
(Hint: the Hamiltonian circuit problem is NPhard even if each vertex
in the graph is incident upon exactly three edges.)

The low degree spanning tree problem is as follows.
Given a graph G and an integer k, does G contain a spanning
tree such that all vertices in the tree have degree at most k
(obviously, only tree edges count towards the degree)?
For example, in the following graph, there is no spanning tree such that all
vertices have degree less than three.

Prove that the low degree spanning tree problem is NPhard
with a reduction from Hamiltonian path.

Now consider the high degree spanning tree problem, which is as follows.
Given a graph G and an integer k, does G contain a spanning
tree whose highest degree vertex is at least k?
In the previous example, there exists a spanning tree of highest degree 8.
Give an efficient algorithm to solve the high degree spanning tree problem,
and an analysis of its time complexity.

(*)
The problem of testing whether a graph G contains a
Hamiltonian path is NPhard, where a Hamiltonian path P is a path
that visits each vertex exactly once. There does not have to be an
edge in G from the ending vertex to the starting vertex of P, unlike
in the Hamiltonian cycle problem.
Given a directed acyclic graph G (a DAG), give an O(n+m)time
algorithm to test whether or not it contains a Hamiltonian path.
(Hint: think about topological sorting and DFS.)

(**)
The 2SAT problem is, given a Boolean formula in 2conjunctive normal form
(CNF), decide whether the formula is satisfiable.
2SAT is like 3SAT, except that each clause can have only two literals.
For example, the following formula is in 2CNF:
Give a polynomialtime algorithm to solve 2SAT.

(*)
It is an open question whether the decision problem ``Is integer n
a composite number, in other words, not prime?" can be computed in
time polynomial in the size of the input.
Why doesn't the following algorithm suffice to prove it is in P,
since it runs in O(n) time?
PrimalityTesting(n)
composite :=
for i := 2 to n1 do
if then
composite :=