0% found this document useful (0 votes)
47 views4 pages

Complexity Theory: Hamiltonian Graphs

This document discusses complexity theory and several NP-complete problems. It begins by defining Hamiltonian graphs and the Hamiltonian (HAM) problem. It then discusses reductions from 3SAT to HAM and from HAM to the travelling salesman (TSP) problem. The document goes on to discuss 3-dimensional matching (3DM) and how 3DM is NP-complete via a reduction from 3SAT. It also briefly mentions the set covering problem and exact cover by 3-sets being NP-complete via a reduction from 3DM.

Uploaded by

Subhasis Maity
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
47 views4 pages

Complexity Theory: Hamiltonian Graphs

This document discusses complexity theory and several NP-complete problems. It begins by defining Hamiltonian graphs and the Hamiltonian (HAM) problem. It then discusses reductions from 3SAT to HAM and from HAM to the travelling salesman (TSP) problem. The document goes on to discuss 3-dimensional matching (3DM) and how 3DM is NP-complete via a reduction from 3SAT. It also briefly mentions the set covering problem and exact cover by 3-sets being NP-complete via a reduction from 3DM.

Uploaded by

Subhasis Maity
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Complexity Theory 1 Complexity Theory 2

Hamiltonian Graphs
Complexity Theory
Lecture 7 Recall the definition of HAM—the language of Hamiltonian graphs.

Given a graph G = (V, E), a Hamiltonian cycle in G is a path in


the graph, starting and ending at the same node, such that every
node in V appears on the cycle exactly once.

Anuj Dawar
A graph is called Hamiltonian if it contains a Hamiltonian cycle.

University of Cambridge Computer Laboratory


The language HAM is the set of encodings of Hamiltonian graphs.
Easter Term 2011

http://www.cl.cam.ac.uk/teaching/1011/Complexity/

Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011

Complexity Theory 3 Complexity Theory 4

Hamiltonian Cycle Travelling Salesman

We can construct a reduction from 3SAT to HAM Recall the travelling salesman problem
Essentially, this involves coding up a Boolean expression as a
graph, so that every satisfying truth assignment to the expression Given
corresponds to a Hamiltonian circuit of the graph. • V — a set of nodes.
• c : V × V → IN — a cost matrix.
This reduction is much more intricate than the one for IND.
Find an ordering v1 , . . . , vn of V for which the total cost:

n−1
X
c(vn , v1 ) + c(vi , vi+1 )
i=1

is the smallest possible.

Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011
Complexity Theory 5 Complexity Theory 6

Travelling Salesman Reduction

As with other optimisation problems, we can make a decision There is a simple reduction from HAM to TSP, mapping a graph
problem version of the Travelling Salesman problem. (V, E) to the triple (V, c : V × V → IN, n), where

 1 if (u, v) ∈ E
The problem TSP consists of the set of triples
c(u, v) =
 2 otherwise
(V, c : V × V → IN, t)
and n is the size of V .

such that there is a tour of the set of vertices V , which under the
cost matrix c, has cost t or less.

Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011

Complexity Theory 7 Complexity Theory 8

Sets, Numbers and Scheduling 3D Matching

It is not just problems about formulas and graphs that turn out to The decision problem of 3D Matching is defined as:
be NP-complete.
Given three disjoint sets X, Y and Z, and a set of triples
Literally hundreds of naturally arising problems have been proved M ⊆ X × Y × Z, does M contain a matching?
NP-complete, in areas involving network design, scheduling, I.e. is there a subset M ′ ⊆ M , such that each element of
optimisation, data storage and retrieval, artificial intelligence and X, Y and Z appears in exactly one triple of M ′ ?
many others.
Such problems arise naturally whenever we have to construct a We can show that 3DM is NP-complete by a reduction from 3SAT.
solution within constraints, and the most effective way appears to
be an exhaustive search of an exponential solution space.
We now examine three more NP-complete problems, whose
significance lies in that they have been used to prove a large
number of other problems NP-complete, through reductions.

Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011
Complexity Theory 9 Complexity Theory 10

Reduction In addition, for every clause c, we have two elements xc and yc .


If the literal v occurs in c, we include the triple
If a Boolean expression φ in 3CNF has n variables, and m clauses,
we construct for each variable v the following gadget. (xc , yc , zvc )

zv1 in M .
z̄v1 z̄v4
xv1 yv1 Similarly, if ¬v occurs in c, we include the triple
yv2 xv4 (xc , yc , z̄vc )
zv2 zv4
yv4 in M .
xv2
yv3 Finally, we include extra dummy elements in X and Y to make the
xv3
numbers match up.
z̄v2 z̄v3
zv3
Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011

Complexity Theory 11 Complexity Theory 12

Exact Set Covering Set Covering

Two other well known problems are proved NP-complete by More generally, we have the Set Covering problem:
immediate reduction from 3DM.
Given a set U , a collection of S = {S1 , . . . , Sm } subsets of
U and an integer budget B, is there a collection of B sets
in S whose union is U ?
Exact Cover by 3-Sets is defined by:
Given a set U with 3n elements, and a collection
S = {S1 , . . . , Sm } of three-element subsets of U , is there a
sub collection containing exactly n of these sets whose
union is all of U ?
The reduction from 3DM simply takes U = X ∪ Y ∪ Z, and S to be
the collection of three-element subsets resulting from M .

Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011
Complexity Theory 13 Complexity Theory 14

Knapsack Reduction

KNAPSACK is a problem which generalises many natural The proof that KNAPSACK is NP-complete is by a reduction from
scheduling and optimisation problems, and through reductions has the problem of Exact Cover by 3-Sets.
been used to show many such problems NP-complete.
Given a set U = {1, . . . , 3n} and a collection of 3-element subsets of
In the problem, we are given n items, each with a positive integer U , S = {S1 , . . . , Sm }.
value vi and weight wi . We map this to an instance of KNAPSACK with m elements each
We are also given a maximum total weight W , and a minimum corresponding to one of the Si , and having weight and value
total value V .
Σj∈Si (m + 1)j−1
Can we select a subset of the items whose total weight does
not exceed W , and whose total value exceeds V ? and set the target weight and value both to
3n−1
Σj=0 (m + 1)j

Anuj Dawar May 16, 2011 Anuj Dawar May 16, 2011

You might also like