## 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)