University of Sussex Informatics
Limits of Computation
Answers for Exercises 8 Dr Bernhard Reus
Problems in P, not in P and NP
Spring 2021
(Lectures 16–18)
1. For which of the four graphs (a-e) given below does such a tour
starting, say, in vertex A exist?
ab
cde
(a) Consider the graphs from question (a) for which a tour as described exists. What do they have in common?
Answer:
All vertices have an even degree (that’s the number of edges going in/out). In the Yes cases above the degree of any vertex is either 2 or 4
(b) Can you guess Euler’s theorem that states the condition on which a tour (in connected graphs) exists? (look at the edges!)
Answer:
If every vertex of a connected graph has even degree then the graph admits an Eulerian circuit.
2. Recall the Max-Flow problem from Lecture 16:
instance: a weighted directed graph G = (V, E, w) (encoding a
1
flow network where w(u, v) ∈ Z describes the maximum capacity offlowfromnodeutonodev),asourcenodes∈V andasink node t ∈ V .
question: What is the maximum flow from s to t in G ?
Reformulate the Max-Flow Problem as an instance of the Lin- ear Programming Problem (Lecture 16, page 20) for the specific example given on Slide 17, Lecture 16 as seen below.
Hint: use flow variables fv,w that
s
23
23
11 31
45
3
Answer: We can perform this representation in general for all network problems represented as graph G = (V,E,c) where c represent the weights of edges which are the capacities.
maximisev∈V fs,v
fu,v ≤cu,v forallu,v∈V
v∈V fv,u =v∈V fu,v forallu∈V \{s,t}
The latter can be rephrased as
v∈V fv,u − v∈V fu,v = 0 for all u ∈ V \ {s, t} which again can be rephrased as two inequalities v∈V fv,u − v∈V fu,v ≤ 0 for all u ∈ V \ {s, t} which is in the required form. and
v∈V fv,u − v∈V fu,v ≥ 0 for all u ∈ V \ {s, t}
which can be brought into the required form by multiplying both sides with −1:
2
describe the flow from node v to node
w. Take into account that flows are
never negative, that they are bounded
by the given capacities, and that the
total flow into a node must be equal to
the total flow out of a node. To start
you off, here is the expression that
needs to be maximised: v∈V fs,v. It
remains for you to give the inequations
(using variables fv,w) that describe the
flow network. 2
t
v∈V fu,v −v∈V fv,u ≤0forallu∈V \{s,t}
Now this tells one how to translate any max flow problem into a liner integer problem. For the concrete example given, you would then write for, e.g. node 2: v∈V fv,2 − v∈V f2,v ≤ 0 and v∈V f2,v − v∈V f2,3 ≤ 0
which gives
fs,2 −f2,4 −f2,5 ≤0andf2,4 +f2,5 −fs,2 ≤0
which is in the required form of an inequalities with a constant on the right hand side. Note that in the solution for this max-flow problem fs,2 = 2, f2,4 = 1, f2,5 = 1
Repeat this for all nodes u ∈ V \ {s, t} to get all inequalities. 3. Show that the Graph Colouring Problem is in NP. To do so:
(a) Sketch a WHILE-verifier for the Graph Colouring Problem. Explain how you would represent the data needed as input and sketch roughly how the program would work.
Answer:
The verifier takes as input an encoding of the graph G = (V,E) and of the number K of colours, and additionally a certificate. There are various ways to represent the graph. Let’s assume here that it is represented as two lists: a list of vertices (nodes), all of which are encoded as numbers, and a list of edges, which are represented as pairs (v1,v2). Note that the data of ((V,E),K) has to be encoded uniquely as a binary sequence but we assume we can encode and decode pairs and lists of numbers. In particular, all numbers are represented in binary. The verifier then must check:
i. whether the certificate C is a list of pairs of numbers that are assumed to be a name of a node and its colour encoded as a number – (vertex,colour).
ii. if (i) is false return false else check whether the colours used in C (in the second position of the pairs) are al- lowed, i.e. one of 1,…,K.
iii. if (ii) is false then return false else for each vertex v ∈ V collect a list L of all the colours of nodes that appear in a edge in E that contains v. The colours can be found
3
in C. If a node is not in C return false immediately. Otherwise check whether the colours in L are different from the colour of v.
iv. if (ii) is false return false else return true.
(b) Show that your verifier above runs in polynomial time in the size of the problem instance.
Answer:
Consider the runtime of each step:
i. This can be done in constant time in the size of the problem instance, i.e. in ((V, E), K).
ii. This can be done in time O(|K|) for the comparisons with K. Note that size of K is logarithmic in K.
iii. The collection of L can be done in time O(|E|). Checking whether the colours are different for each vertex can be checked in O(|V |2)
iv. This can clearly be done in constant time.
So if we add all those time requirements up we get O(|V | + |K|+|E|+|V |2) and thus we have a polynomial runtime in the size of the problem instance ((V, E), K) which is |((V, E), K)| = |V|+|E|+|K|.
Note that you can implement the checking da bit differently, also more efficiently. It’s important that your program ”sketch” is clear enough and that you get a good description of the runtime and argue it’s polynomial.
4