This summative assessment is about matchings and vertex covers in graphs. You must carefully and clearly justify all your answers.

In the following let G = (V ,E) be an undirected graph. An edge e ∈ E which has the vertices u and v as endpoints is denoted by e = uv.

A matching in the undirected graph G = (V ,E) is a set of non-adjacent edgesin G. Let μ(G) be the maximum (i.e. the largest possible) number of edges in a matching in G. For instance, the cycle Cn  on n vertices satisfies μ(Cn ) = ⌊n/2⌋ .

A vertex cover in the undirected graph G = (V ,E) is a subset of vertices S which intersects any edge: for any e = uv ∈ E, either u or v (or both) is in S. Let τ(G) be the minimum size of a vertex cover in G. For instance, the cycle Cn  satisfies τ(Cn ) = ⌈n/2⌉ .

Question 1 (30 marks). Express μ(G) and τ(G) as optimal values of two integer programs whose relax- ations are dual to each other. Justify your answer.

Recall that a graph G is bipartite if its vertex set can be partitioned into two independent sets.

Question 2 (20 marks). Prove that if G is bipartite, then μ(G) = τ(G). Hint: you may use the max-flow min-cut theorem.

A fractional matching of G is any feasible solution of the linear relaxation of the integer program above for matching (see Question 1). The maximum value of a fractional matching is denoted as μ∗(G), it is the optimal value of the relaxation of either integer programs for matching and for vertex cover in Question 1. For instance, μ∗(Cn ) = n/2.

Question 3 (20 marks). Using the IP and LP formulations of Question 1, write a Python program, which for a given graph G computes a maximum matching, a minimum vertex cover, and a maximum fractional matching of G.

You must use the CBC solver available from the Python package MIP. The program input should be a Graph object from the Python package networkx, and the output should be printed to the screen.

For every vertex v ∈ V, we denote by N(v) = {u ∈ V : uv ∈ E} the neighborhood of v, i.e. N(v) is the set of all vertices u in the graph such that there is an edge between u and v. Note that no vertex v can belong to its own neighborhood,i.e. v ∉ N(v) for every v ∈ V.

A vertex cover S of a graph G is minimal if there is no vertex cover T of G such that T ⊂ S.

Question 4 (20 marks). Let G = (V ,E) be a graph on the vertices V = {1, . . . , n}. For every vertex i ∈ V let xi ∈ {0, 1} be a binary variable, and denote by x = (x1 , x2 , . . . , xn) the n-vector of these binary values.  For any i ∈ V, define the function fi  : {0, 1}n → {0, 1} such that, for every x = (x1 , x2 , . . . , xn) ∈ {0, 1}n, we have:

fi(x) = ， (¬xj).

j∈N(i)

Then define the function f : {0, 1}n  → {0, 1}n  (a generalized cellular automaton) such that, for every x = (x1 , x2 , . . . , xn) ∈ {0, 1}n, we have:

f(x) = (f1 (x), . . . , fn (x)).