Summer 2020
1. Prove, that the Max Independent Set (finding set of vertices in a graph, no two of which
are adjacent) is in class NP. To do that, provide:
a) Optimization formulation (max/min)
b) Decision formulation (yes/no, often with extra parameter)
c) Polynomial-size certificate (Merlin-Arthur, Merlin gives a hint)
d) Polynomial time verification algorithm (Merlin-Arthur, Arthur checks the hint)
2. For the 3-CNF
f = (x’ +y’+z)& (x+y’+z’)&(x+y+z’)& (x’+y+z)&(x’+y+z’) &(x+y+z)
where “+” is or, “&” is and operations, “ ’ ” is negation.
a) give 0-1 assignment to variables such that
f=1 x= _ y= z= f=0 x= y= z= _
b) Draw the corresponding graph and mark the maximum independent set.
(you can draw on paper, scan and insert here)
3.
In the following graph find (if several of same size exists – write just one)
- Maximum Independent Set___________________________
- Minimum Vertex Cover___________________________
- Maximum Clique __________
4
8
5
7
1
6
9
2
3
4.
We studied complexity classes P and NP, as well as NP-complete problems. The relations
between those classes are shown in the following diagram.
Are there any problems that belong to the class NP, but lay outside both P and NP-complete (i.e.
in the purple area of the diagram)?
Can you name any such problem (or at least a problem that is suspected to belong to the purple
area)?
Find a reference to a paper or a webpage.
5.
There is a group of n people, for every person in this group there is a list of people he/she likes.
One of the people has a book that everybody wants to read. Every person can lend the book to
other person, but only if he/she likes this person.
You need to find out, is it possible to organize transfer of the book between people in such a way,
that everybody will have it exactly ones and in the end it will return to its owner?
Represent this problem as an algorithmic problem. What is this algorithmic
problem? Is it possible to solve it in a polynomial time?
Important note: you are not asked to solve it.
Sample Solution