闪电代写 -代写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 2018

COMP394001

Graph Algorithms and Complexity Theory

Question 1

(a) Suppose directed graphs are already deﬁned. Deﬁne

● network [2 marks]

● capacity function [1 mark]

● ﬂow [3 marks]

● s, t-cut [2 marks]

(b) Determine a maximum ﬂow and a minimum cut (state the partition of the vertex set and edges in the cut) in the following network. Numbers next to edges denote capacities. Show your work. [12 marks]

[question 1 total: 20 marks]

Question 2

This is a question about matchings in undirected graphs

(a) Deﬁne

(i) a matching, [1 mark]

(ii) a maximum matching, and [1 mark]

(iii) an augmenting path. [2 marks]

(b) Berge’s lemma says that M is a maximum matching of G if and only if there is no M-augmenting path in G. Prove this lemma. You may assume that the symmetric diﬀerence between any two matchings consists of alternating paths and alternating cycles. [6 marks]

(c) Illustrate Edmonds’ blossom algorithm at the graph depicted below. An initial matching is indicated by bold lines. [10 marks]

[question 2 total: 20 marks]

Question 3

This question deals with polynomial-time many-one reducibility.

(a) Deﬁne the relation <m(p) . [5 marks]

(b) Prove that <m(p) is reﬂexive, that is, show for all decision problems Π that Π <m(p) Π holds. [5 marks]

(c) Prove that <m(p) is transitive, that is, show for all decision problems Π 1 , Π2 and Π3 that if Π 1 <m(p) Π2 and Π2 <m(p) Π3 hold then Π 1 <m(p) Π3 holds as well. [10 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:

Mls (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 Mls is NP-complete. For integers i with 1 < i < 6 we consider functions fi that map instances (G, k) of Mls to other such instances. Which of these functions are polynomial transformations from Mls 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.

For two graphs G = (V, E) and H = (U, F) with V U U = ∅ let G + H = (V u U, E u F). If V U 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.