-
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 NP-complete 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 NP-complete 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 NP-hard 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 NP-hard.
(Hint: the Hamiltonian circuit problem is NP-hard 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 NP-hard
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 NP-hard, 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 2-SAT problem is, given a Boolean formula in 2-conjunctive normal form
(CNF), decide whether the formula is satisfiable.
2-SAT is like 3-SAT, except that each clause can have only two literals.
For example, the following formula is in 2-CNF:
Give a polynomial-time algorithm to solve 2-SAT.
-
(*)
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 n-1 do
if then
composite :=