闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

January 2019

COMP394001

Graph Algorithms and Complexity Theory

Question 1

(a) Determine a maximum ﬂow 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. [12 marks]

(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-ﬂow min-cut theorem to show that a cut (X, Y) is minimum if and only if there is a ﬂow 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. [8 marks]

[question 1 total: 20 marks]

Question 2

This is a question about matchings in undirected graphs

(a) Deﬁne

(i) a matching [2 marks]

(ii) a maximal matching [1 mark]

(iii) a maximum matching [1 mark]

(iv) a perfect matching [1 mark]

(v) an augmenting path. [2 marks]

(b) State Berge’s lemma about matchings. [1 mark]

(c) Illustrate Edmonds’ blossom algorithm for the graph depicted below. An initial match-ing is indicated by bold lines. [12 marks]

[question 2 total: 20 marks]

Question 3

This question deals with polynomial-time many-one reducibility. Assume the complexity classes P and NP are already deﬁned.

(a) Deﬁne the relation [5 marks]

(b) Deﬁne what it means for a decision problem to be NP-complete. [5 marks]

[question 3 total: 20 marks]

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:

M1s (maximum independent set) is deﬁned by

instance: An undirected graph G on n > 0 vertices and a natural number k . question: Is α(G) > k?

It is known that M1s is NP-complete. For integers i with 1 < i < 6 we consider functions fi that map instances (G, k) of M1s to other such instances. Which of these functions are polynomial transformations from M1s to itself? Your answer can be an unconditional “yes” or “no”, or it can depend on whether P = NP or P NP. A justiﬁcation is not required.

(a) f1 (G, k) = (G + G, 2k) [3 marks]

(b) f2 (G, k) = (G + Kn, k + 1) [3 marks]

(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. [4 marks]

(e) f5 (G, k) = f4 (G, k) if G is bipartite and f5 (G, k) = (G, k) otherwise. [4 marks]

(f) f6 (G, k) = (K1 , 1) if α(G) > k and f6 (G, k) = (K1 , 2) if α(G) < k . [3 marks]

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.