University of Sussex Informatics
Limits of Computation
Exercises 8
Problems in P and not known to be in P
(Lectures 16–18)
Spring 2021
1. Consider the Eulerian Circuit Problem (also Postman Problem): “For a given (undirected) graph, is there a round trip that visits each edge exactly once?”
(a) For which of the four graphs (a-e) given below does such a tour starting, say, in vertex A exist?
ab
cde
(b) Consider the graphs from question (a) for which a tour as described exists. What do they have in common?
(c) Can you guess Euler’s theorem that states the condition on which a tour (in connected graphs) exists? (look at the edges!)
2. Recall the Max-Flow problem from Lecture 16:
instance: a weighted directed graph G = (V, E, w) (encoding a 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 ?
1
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
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
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.
(b) Show that your verifier above runs in polynomial time in the size of the problem instance.
s
23
23
11 31
45
3
2
t