1. An independent set of a graph G = (V, E) is a subset V 0 ? V of vertices such
ID: 656090 • Letter: 1
Question
1. An independent set of a graph G = (V, E) is a subset V 0 ? V of vertices such that each edge in E is incident on at most one vertex in V 0 . The independent set problem is to find a maximum-size independent set in G. A vertex cover of a graph G = (V, E) is a subset of vertices V 0 ? V such that every edge in E contains at least one vertex from V 0 . The vertex cover problem is to find a vertex cover of minimum size in G. (a) Formulate the decision version of the independent set problem. We will refer to this as ISET. (b) Formulate the decision version of the vertex cover problem. We will refer to this as VERTEX-COVER. (c) Show that ISET ?P VERTEX-COVER.
2. Given an integer m
Explanation / Answer
To show that any problem A is NP-Complete, we need to show four
things:
(1) there is a non-deterministic polynomial-time algorithm that solves A,
(2) any NP-Complete problem B can be reduced to A,
(3) the reduction of B to A works in polynomial time,
(4) the original problem A has a solution if and only if B has a solution.
We now show that SET-PARTITION is NP-Complete.
(1) SET-PARTITION ? NP: Guess the two partitions and verify that the two
have equal sums.
(2) Reduction of SUBSET-SUM to SET-PARTITION: Recall SUBSET-SUM is
defined as follows: Given a set X of integers and a target number t, find a subset
Y ? X such that the members of Y add up to exactly t. Let s be the sum of
members of X. Feed X? = X ? {s ? 2t} into SET-PARTITION. Accept if and
only if SET-PARTITION accepts.
(3) This reduction clearly works in polynomial time.
(4) We will prove that hX, ti ? SUBSET-SUM iff hX?i ? SET-PARTITION.
Note that the sum of members of X? is 2s ? 2t.
?: If there exists a set of numbers in X that sum to t, then the remaining numbers
in X sum to s ? t. Therefore, there exists a partition of X? into two such that
each partition sums to s ? t.
?: Let
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.