DATA STRUCTURES AND ALGORITHM ANALYSIS
COMP 3804
Assignment 4
Date Due: Friday, Dec 11, 2020
Time Due: 11:59pm
Your assignment should be typed (or neatly printed) and submitted on CuLearn.
For your NP-Completeness proofs, you may use any of the NP-Complete problems listed in Chapter 12 of Jeff
Erickson’s textbook for your reduction.
1. (10 pts) Let G = (V, E) be an undirected graph where each edge e = {u, v} has a weight wt(u, v) > 0. Let G
be 2-connected (i.e. between every pair of vertices, there exists 2 vertex disjoint paths). Prove or disprove the
following: Let u, v be two arbitrary vertices in G. Let S(u, v) be the shortest path from u to v in G. Since G is
2-connected, does there always exist another path from u to v, denoted P(u, v), such that S(u, v) and P(u, v)
are vertex disjoint? Vertex disjoint means that the only vertices shared by S(u, v) and P(u, v) are u and v.
2. (10 pts) Let G = (V, E) be an undirected graph where each edge e = {u, v} has a weight wt(u, v) > 0. Let T
be a minimum spanning tree of G. Let H be a connected subgraph of G. Prove or disprove that there exists a
minimum spanning tree T
0 of H, such that every edge of T ∩ H is in T
0
.
3. (10 pts) Let G = (V, E) be a directed graph where each edge e = {u, v} has weight wt(u, v) > 0 or wt(u, v) < 0
(i.e. no edge has a weight of zero). Prove that deciding if G has a directed cycle such that the sum of the
weights of the edges in the cycle is zero, is an NP-Complete problem.
4. (10 pts) Let G = (V, E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph
induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v ∈ S provided
that {u, v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of
G, that is G[V − K] has no edges. Prove that finding the smallest killer set of G is an NP-Complete problem.