Description
Q1: Given an undirected graph G = (V, E), and positive integer k, the max-degree-spanning-tree
problem asks whether G has a spanning tree whose degree is at most k. The degree of a spanning
tree T is defined as the maximum number of neighbors a node has within the tree (i.e., a node
may have many edges incident on it in G, but only some of them get included in T). Show that
the max-degree-spanning-tree (MDST) problem is NP-complete. (20pts)
Q2: The k-cycle-decomposition problem for any k > 1 works as follows. The input consists of a
connected graph G=(V, E) and k positive integers a1
, …, ak < |V|. The goal is to determine
whether there exist k disjoint cycles of sizes a1
, …, ak respectively, s.t., each node in V is
contained in exactly one cycle. Show that this problem is NP-complete (for any k > 1). (20 pts)
Q3. Given a graph G = (V, E) with an even number of vertices as the input, the HALF-IS
problem is to decide if G has an independent set of size |V| / 2. Prove that HALF-IS is in
NP-Complete. (20pts)
