COS 341, November 12, 1997Handout Number 16
Reducibility Proof
Problem A is said to be polynomial-time reducible to Problem
B if, for some fixed integer k,
the following is true. Given an input I of size n for
A, one can construct efficiently an input I' of size 
for B such that the answer to I' is YES if and only if
the answer to I is YES.
In this course when you are asked to show that A is polynomial-time reducible to B, we do not require a proof with complete details. However, it should contain at least the following elements.
First, the construction of I' from I should be unambiguous, and it has to be convincing that the size of I' is at most a polynomial function of the size of I'. (In principle, the construction needs to be doable in polynomial time, but we will not ask you to give a proof.)
Second, you need to give a convincing argument that the answer to I' is YES if and only if the answer to I is YES.
As an example, we show that the Eulerian cycle
problem is polynomial-time reducible to
the Hamiltonian cycle problem. Let G=(V, E)
be a graph where |V|=n be the input
to the Eulerian cycle problem. The size of
G is the number of bits needed to
encode V and E, and thus at most 
.
We construct G' = (V',E') as an input
to the Hamiltonian cycle problem as follows.
For each 
, construct
three vertices 
;
let V' be the set of all such vertices.
Thus, 
.
There will be two kinds of edges in E':
first, for each , create
two edges 
, 
;
second, for each 
, if there are
s 
incident to i in G,
create all the 
edges among
for these s e's. Note that
the size of G' is at most 
.
Furthermore, the construction of G' can be
done efficiently (this last assertion you don't need to
justify rigorously for this course).
It remains to show that
Claim: G has an Eulerian cycle if and only if G' has a Hamiltonian cycle.
Let m = |E|.
Suppose G has an Eulerian cycle 
where 
has 
as its two
endpoints. Then the following is clearly a Hamiltonian
cycle in G' (just check that all vertices in
V' appear, and that all consecutive
vertices are connected by edges in E'):
This proves the claim in one direction.
Conversely, assume that G' has a Hamiltonian
cycle C in which the m=|E| vertices of the form 
( )
appear in the circular order
.
Note that, since each has only two
edges in E', these two edges must be used
in the Hamiltonian cycle to enter and leave
. Since there are only 3m
vertices in V', it follows that the cycle C must be
of the form
where has 
as
its two endpoints in G.
By definition of cycle, there must be
an edge in E' connecting the
two vertices
for each 
,
implying that 
.
But this
means that is an Eulerian cycle in G.
This proves the other direction.