COMP394001 Graph Algorithms and Complexity Theory 2019
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
2019
COMP394001
Graph Algorithms and Complexity Theory
Question 1
(a) Determine a maximum flow and a minimum cut in the following network. Numbers
next to edges denote capacities. As part of your answer state the partition of the vertex set and edges across the cut. Show your work.
(b) Let (A, B) and (C, D) be minimum cuts in a network (G, s, t) with capacities c. Show
that (A n C, B u D) is also a minimum cut.
Hint: Use the max-flow min-cut theorem to show that a cut (X, Y) is minimum if and only if there is a flow f in the network such that
● for all edges (x, y) with x e X and y e Y we have f(x, y) = c(x, y), and
● for all edges (y, x) with x e X and y e Y we have f(y, x) = 0.
and use this property to prove the assertion.
Question 2
This is a question about matchings in undirected graphs
(a) Define
(i) a matching
(ii) a maximal matching
(iii) a maximum matching
(iv) a perfect matching
(v) an augmenting path.
(b) State Berge’s lemma about matchings.
(c) Illustrate Edmonds’ blossom algorithm for the graph depicted below. An initial match-ing is indicated by bold lines.
Question 3
This question deals with polynomial-time many-one reducibility. Assume the classes P and NP are already defined.
complexity
(a) Define the relation
(b) Define what it means for a decision problem to be NP-complete.
(c) Prove that if one NP-complete problem belongs to P then P = NP.
Question 4
Let α(G) denote the maximum size of an independent set of the graph G. We consider the following decision problem related to this parameter:
M15 (maximum independent set) is defined by
instance: An undirected graph G on n > 0 vertices and a natural number k . question: Is α(G) > k?
It is known that M15 is NP-complete. For integers i with 1 < i < 6 we consider functions fi that map instances (G, k) of M15 to other such instances. Which of these functions are polynomial transformations from M15 to itself? Your answer can be an unconditional “yes” or “no”, or it can depend on whether P = NP or P 
NP. A justification is not required.
(a) f1 (G, k) = (G + G, 2k)
(b) f2 (G, k) = (G + Kn, k + 1)
(c) f3 (G, k) = (G + K2n, k + 1)
(d) f4 (G, k) = (K1 , 1) if G has no matching of size n · k + 1 and f4 (G, k) = (K1 , 2) if this is not the case.
(e) f5 (G, k) = f4 (G, k) if G is bipartite and f5 (G, k) = (G, k) otherwise.
(f) f6 (G, k) = (K1 , 1) if α(G) > k and f6 (G, k) = (K1 , 2) if α(G) < k .
A hint on notation: For two graphs G = (V, E) and H = (U, F) with V n U = ∅ let G + H = (V u U, E u F). If V n U 
∅ we replace one of the graphs by an isomorphic copy such that their vertex sets become disjoint. Especially, G + G is the union of two disjoint copies of G. By Kn we denote the complete graph on n vertices.
2022-01-15