NP, and NP-Complete Problems…
Dr. Ajay Pratap
Asst. Professor, Dept. of CSE, IIT (BHU), Varanasi, India
ajay.cse@iitbhu.ac.in
Sequencing problems
Euler tour is in P
⚫ Euler tour: An Euler tour of a
connected, directed gaph is a cycle that
traverses each edgeof G exactly once, Hamiltonian Non-Hamiltonian
although it is allowed to visit each vertex
more than once.
⚫ We can determine whether a graph has an Eulerian
Euler tour in only O(E) time and, in fact,
we can find the edges of the Euler tour in
O(E) time.
HAMILTON-CYCLE. Given an undirected graph G = (V, E),
Non-Eulerian
does there exist a cycle Γ that visits every node
exactly once?
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (Vol. 3, pp. 624-
642). Cambridge: MIT press.
Hamilton cycle
HAMILTON-CYCLE. Given an undirected graph G = (V, E), does there exist a
cycle Γ that visits every node exactly once?
yes
Home work
• Prove than Hamilton cycle is a Hard problem.
Poly-time reductions
Partitioning problems
3-dimensional matching
3D-MATCHING. Given n instructors, n courses, and n times, and a list of the
possible courses and times each instructor is willing to teach, is it possible
to make an assignment so that all courses are taught at different times?
instructor course time
Wayne COS 226 TTh 11–12:20
Wayne COS 423 MW 11–12:20
Wayne COS 423 TTh 11–12:20
Tardos COS 423 TTh 3–4:20
Tardos COS 523 TTh 3–4:20
Kleinberg COS 226 TTh 3–4:20
Kleinberg COS 226 MW 11–12:20
Kleinberg COS 423 MW 11–12:20
3-dimensional matching
3D-MATCHING. Given 3 disjoint sets X, Y, and Z, each of size n and a set
T ⊆ X × Y × Z of triples, does there exist a set of n triples in T such that
each element of X ∪ Y ∪ Z is in exactly one of these triples?
X = { x1, x2, x3 }, Y = { y1, y2, y3 }, Z = { z1, z2, z3 }
T1 = { x1, y1, z2 }, T2 = { x1, y2, z1 }, T3 = { x1, y2, z2 }
T4 = { x2, y2, z3 }, T5 = { x2, y3, z3 },
T7 = { x3, y1, z3 }, T8 = { x3, y1, z1 }, T9 = { x3, y2, z1 }
an instance of 3d-matching (with n = 3)
Remark. Generalization of bipartite matching.
3-dimensional matching
3D-MATCHING. Given 3 disjoint sets X, Y, and Z, each of size n and a set
T ⊆ X × Y × Z of triples, does there exist a set of n triples in T such that
each element of X ∪ Y ∪ Z is in exactly one of these triples?
Theorem. 3-SAT ≤ P 3D-MATCHING.
Pf. Given an instance Φ of 3-SAT, we construct an instance of 3D-MATCHING
that has a perfect matching iff Φ is satisfiable.
Homework: Read and
understand the full proof
from the book:
Graph Coloring
3-colorability
3-COLOR. Given an undirected graph G, can the nodes be colored black,
white, and blue so that no adjacent nodes have the same color?
yes instance
59
Intractability:
How difficult to solve 2-C OLOR ?
A. O(m + n) using BFS or DFS.
B. O(mn) using maximum flow.
C. Ω(2n) using brute force.
D. Not even Tarjan knows.
60
BFS
DFS
Application: register allocation
Register allocation. Assign program variables to machine registers so that
no more than k registers are used and no two program variables that are
needed at the same time are assigned to the same register.
Interference graph. Nodes are program variables; edge between u and v
if there exists an operation where both u and v are “live” at the same time.
Observation. [Chaitin 1982] Can solve register allocation problem iff
interference graph is k-colorable.
Fact. 3-COLOR ≤ P K-REGISTER-ALLOCATION for any constant k ≥ 3.
Application: 5G
• Ajay Pratap, Ragini Gupta, Venkata Sriram Siddhardh Nadendla, Sajal K. Das, "Bandwidth-Constrained
Task Throughput Maximization in IoT-enabled 5G Networks," Pervasive and Mobile
Computing, Volume 69, pp.101281, 2020
• Ajay Pratap, Ragini Gupta, Venkata Sriram Siddhardh Nadendla, Sajal K. Das “On Maximizing Task
Throughput in IoT-enabled 5G Networks under Latency and Bandwidth Constraints”, in IEEE
International Conference on Smart Computing (SMARTCOMP), pp. 217-224, June 12-14, 2019,
Washington D.C . , USA (Best Paper Candidate Award).
• Ajay Pratap, Rajiv Misra, Sajal K. Das “Resource Allocation to Maximize Fairness and Minimize
Interference for Maximum Spectrum Reuse in 5G Cellular Networks” in 19th IEEE International
Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), pp.1-9, June 12-
15, 2018, Chania, Greece.
• Ajay Pratap, Rajiv Misra, Sajal K. Das “Maximizing Fairness for Resource Allocation in Heterogeneous
5G Networks”, IEEE Transactions on Mobile Computing, vol. 20, no. 2, pp. 603-619, 2021
3-satisfiability reduces to 3-colorability
Theorem. 3-SAT ≤ P 3-COLOR.
Pf. Given 3-SAT instance Φ, we construct an instance of 3-COLOR that
is 3-colorable iff Φ is satisfiable.
3-satisfiability reduces to 3-colorability
Construction.
(i) Create a graph G with a node for each literal.
(ii) Connect each literal to its negation.
(iii) Create 3 new nodes T, F, and B; connect them in a triangle.
(iv) Connect each literal to B.
(v) For each clause Cj, add a gadget of 6 nodes and 13 edges.
to be described later
T F
B
3-satisfiability reduces to 3-colorability
3-satisfiability reduces to 3-colorability
3-satisfiability reduces to 3-colorability
3-satisfiability reduces to 3-colorability
Poly-time reductions
constraint satisfaction
3-SAT
INDEPENDENT-SET DIR-HAM-CYCLE 3-COLOR SUBSET-SUM
VERTEX-COVER HAM-CYCLE KNAPSACK
SET-COVER
packing and covering sequencing partitioning numerical
Numerical Problems
Subset sum
SUBSET-SUM. Given n natural numbers w1, …, wn and an integer W, is there a
subset that adds up to exactly W ?
Ex. { 215, 215, 275, 275, 355, 355, 420, 420, 580, 580, 655, 655 }, W = 1505.
Yes. 215 + 355 + 355 + 580 = 1505.
Subset sum
Theorem. 3-SAT ≤ P SUBSET-SUM.
Pf. Given an instance Φ of 3-SAT, we construct an instance of SUBSET-SUM
that has a solution iff Φ is satisfiable.
3-satisfiability reduces to subset sum
3-satisfiability reduces to subset sum
3-satisfiability reduces to subset sum
SUBSET SUM REDUCES TO KNAPSACK
Poly-time reductions
Karp’s 20 poly-time reductions from satisfiability
Dick Karp (1972)
1985 Turing Award
Travelling Salesman Problem (TSP)
13,509 cities in the United States
http://www.math.uwaterloo.ca/tsp
11,849 holes to drill in a programmed logic array
http://www.math.uwaterloo.ca/tsp
Millennium Problems
Millennium Problems
⚫ The Millennium Prize Problems are seven problems in mathematics that
were stated by the Clay Mathematics Institute on May 24, 2000.
⚫ One of 7 Millennium Problems for which Clay Math Institute awards
$1,000,000 i.e., US$1 million prize
⚫ One-million dollar (*) question: P = NP ?
⚫ almost all researchers think P ≠ NP
https://www.claymath.org/millennium-problems
https://www.claymath.org/millennium-problems/millennium-prize-problems
https://en.wikipedia.org/wiki/Millennium_Prize_Problems
Millennium Problems
⚫ Yang–Mills and Mass Gap
⚫ Riemann Hypothesis
⚫ P vsNP Problem: If it is easy to check that asolution to aproblem is correct, is it
also easy to solve the problem?This is the essence of the P vs NP question.Typical
of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit,
how can one do this without visiting a city twice? If you give me a solution, I can
easily check that it is correct. But I cannot so easily find a solution.
⚫ Navier–Stokes Equation
⚫ Hodge Conjecture
⚫ Poincaré Conjecture
⚫ Birch and Swinnerton-Dyer Conjecture
https://www.claymath.org/millennium-problems
Millennium Problems
⚫ To date, the only Millennium Prize problem to have been solved is the
Poincaré conjecture,
⚫ Acentury passed between its formulation in 1904 by Henri Poincaré and its
solution by Grigoriy Perelman, announced in preprints posted on ArXiv.org
in 2002 and 2003.
⚫ Grigoriy Perelman is the Russian mathematician Grigori Perelman.
⚫ He declined the prize money.
⚫ Perelman was selected to receive the Fields Medal for his solution, but he
declined the award.
https://www.claymath.org/millennium-problems/poincar%C3%A9-conjecture
https://en.wikipedia.org/wiki/Millennium_Prize_Problems
Acknowledgment
• Some of the contents are taken from Dr.Animesh Chaturvedi’s PPT
• Some Contents are taken from Lecture slides by Kevin Wayne
Copyright © 2005 Pearson-Addison Wesley
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
• Some contents are taken from MIT Lecture notes.
Acknowledgment
Thank you!
