Guidelines:  (read fully!!)

● Your assignment solution must be submitted as a typed PDF document. Scanned handwritten solutions, solutions in any other format,  or unreadable solutions will  not be accepted or marked.   You  are encouraged to learn the LATEX typesetting system and use it to type your solution.  See the course website for LATEX resources.

● To submit this assignment, use the MarkUs system, at URL https://markus.teach.cs.toronto. edu/2023-01

● This is a group assignment. This means that you can work on this assignment with at most one other student. You are encouraged to work with a partner. Both partners in the group should work on and arrive at the solution together. Both partners receive the same mark on this assignment.

● Work on all problems together. For each problem, one of you should write the solution, and one should proof-read and revise it. The first page of your submission must list the name, student ID, and UTOR email address  of both group members.  Your solution should also list, for each problem, which group member wrote the problem, and which group member proofread and revised it.

● You may not consult any other resources except:  your partner; your class notes; assigned readings. Consulting any other resource,  or collaborating with students  other than your group partner, is  a vio- lation of the academic integrity policy!

● You may use any data structure, algorithm, or theorem previously studied in class, or in one of the prerequisites of this course, by just referring to it, and without describing it.  This includes any data structure, algorithm, or theorem we covered in lecture, in a tutorial, or in any of the assigned readings. Be sure to give a precise reference for the data structure/algorithm/result you are using.

● Unless stated otherwise, you should justify all your answers using rigorous arguments.  Your solution will be marked based both on its completeness and correctness, and also on the clarity and precision of your explanation.

Question 1.  (10 marks)

In this question, let G = (V, E) be an undirected, unweighted, connected graph with n vertices,  represented as an adjacency matrix.  Below, let us say that (S, S) is a non-trivial cut  of V if S  0 and S   0, where S = V \ S is the complement of S in V .  Recall the notation E(S, S) = {(u, v) e E : u e S, v e S} for the edges cut by (S, S).

Part a.  (5 marks)

Let r > 1 be an integer, and let n  > r + 1. Let (S, S) be a non-trivial cut of G such that there are at most r _ 1 distinct non-trivial cuts (T, T) for which IE(T, T)I < IE(S, S)I.  Suppose we run the CoNTRAcT1oN algorithm until r + 1 (super-)nodes remain, i.e. we contract n _ r _ 1 random edges, each chosen uniformly among surviving edges.  Suppose that the edges of G that the algorithm contracts are e1 , e2 , . . . , en -r - 1 , in this order.  Let Ai  be the event that ei  e/ E(S, S), i.e., that the i-th contracted edge is not in E(S, S), and prove that

P(A1  and A2  and  . . .  and An -r - 1 ) >

[Solution]         

Let k = IE(S,  S)I.  Suppose that the edges contracted, in order, are e1 , . . . , en -r - 1 .  Let Ai  be the event that ei  e/ E(S, S). Let Ei  be edges that still have endpoints in different supernodes after i _ 1 contractions (E0  = E). Then

k  

P(Ai  I A1 , . . . , Ai - 1 ) = 1 _

Since setting T to be the nodes of G corresponding to a single supernode gives us one possible non-trivial cut, and each super-node corresponds to a different cut, we have that k is less than or equal to the degrees of all but r _ 1 supernodes. Note that after i _ 1 contractions, we have n _ i + 1 supernodes, so this means that k is less than or equal to the degrees of the n _ i _ r + 2 supernodes with largest degrees.  Moreover, 2IEi I equals the sum of all the degrees of the supernodes, which is larger than or equal to the sum of the largest n _ i _ r + 2 degrees. Therefore, 2IEi I > (n _ i _ r + 2)k, so we have

2                 n _ i _ r   

n _ i _ r + 2      n _ i _ r + 2

Now we have that the probability that no edge of E(S, S) is contracted is

P(A1 , . . . , An -r - 1 ) = n _ r + 1 .    n _ r    . n _ r _ 1 . . . 4 . 3 = (n _ r + 1)(n _ r)

Part b.  (5 marks)

Describe an algorithm, based on the CoNTRAcT1oN algorithm, which runs in time O(n4 ), and, with prob- ability at least 2/3, outputs the three smallest cuts of G.  I.e., the algorithm should output three distinct non-trivial cuts (S1 , S1 ), (S2 , S2 ), (S3 , S3 ) such that any other non-trivial cut (T, T) of G satisfies

3

Describe your algorithm clearly, and justify its correctness and running time.

[Solution]

We will run the CoNTRAcT1oN algorithm until 4 supernodes remain. Then we record the three smallest cuts out of the 7 possible cuts indiced by a cut of the contracted multigraph. We repeat this process T times, and keep track of the three smallest cuts out of all cuts we have seen in all T runs. Each run of CoNTRAcT1oN can be implemented in time O(n2 ) as we have seen in a tutorial. Therefore, the total running time is O(Tn2 ), and we will show that it suffices to take T = O(n2 ). 

Let us fix three cuts (S1 , S1 ), (S2 , S2 ), (S3 , S3 ) such that all other cuts are at least as large as the largest of them.  It is enough to show that, with probability at least 2/3, each of these cuts has survived in at least one of the T runs of the CoNTRAcT1oN algorithm.

By the previous sub-problem, the probability that (Si , Si ) has survived in at least one of the T runs is at

least

1 _ ╱ 1 _ 、T  > 1 _ e-2T/((n -i+1)(n -i)  > 1 _ e-2T/(n(n - 1)) .

So, setting T >  gives that this probability is at least 8/9. By a union bound, the probability this happens for all three cuts (Si , Si ) is at least 2/3.

Question 2.  (13 marks)   Recall that a path in an undirected graph G = (V, E) is simple if no vertices on the path are repeated.  Similarly a simple k-cycle in G is sequence of distinct vertices v1 , . . . , vk  in V such

that for any i < k the edge (vi , vi+1) is in E, and also the edge (vk , v1 ) is in E, as well. Part a.  (3 marks)

Prove that, for every rational number 0  < ε < 1, and for k =  [nε 1, the problem of deciding whether a connected undirected graph G = (V, E) with n nodes has a simple k-cycle is NP-hard.

[Solution]

We give a Karp reduction from the HAMCvcLE problem on connected graphs. Suppose we are given a graph G0  = (V0 , E0 ) with n0  vertices and m0  edges. By definition, this graph has a Hamiltonian cycle if and only if it contains a simple cycle of length n0 .  Let n be such that  [nε 1 = n0 :  note that n is polynomial in n0 . We create a graph G = (V, E) with n vertices and n = m0 + n _ n0  edges, by adding n _ n0  new vertices to G0  that form a path, and connecting the first vertex in the path to an arbitrary node of G0 . The reduction clearly runs in polynomial time.

Clearly the graph G is connected if G0  is connected.  Moreover, if G0  has a simple cycle of length n0  (i.e., a Hamiltonian cycle), then G also has a simple cycle of length n0  = [nε 1, because G0  is a subgraph of G. In the converse direction, supppose G has a simple cycle of length n0 .  Then we claim this cycle must only use edges and vertices in G0 .  This is because no new vertex that we added is contained in any cycle in G since every new edge that we added is a bridge (removing it disconnects the graph, and no bridge can be

contained in a simple cycle. Therefore, any cycle in G must also be a cycle in G0 .

Part b.  (5 marks)

Let G = (V, E) be an undirected graph with n nodes.  Let π be a permutation of V ; i.e.  π assigns each vertex v e V a distinct integer in {1, . . . , n}.  A π-increasing k-cycle in G is a cycle whose vertices can be listed as v1 , . . . , vk  so that π(vi ) < π(vj ) for all i < j .  (Notice that such a cycle must be simple.)  Give an algorithm that, given G and π, decides whether G has a π-increasing k-cycle in time O(kn3 ). Describe your

algorithm clearly and argue why it is correct and runs in the required time.

H1NT: You can use dynamic programming or matrix multiplication.

[Solution]

Let us define an n × n matrix B, whose rows and columns correspond to the vertices of G. We define buv  = 1 if (u, v) e E and π(u) < π(v).  If either of these conditions is false, we define buv   = 0.  This graph can be constructed from π and the adjacency matrix of G in time O(n2 ).  Let us now define a length b simple path in G with vertices v1 , . . . , ve  to be π-increasing if for any i < j , π(vi ) < π(vj ). We claim that there is a π-increasing path in G of length exactly b from u to v if and only if (Be )uv  > 0.  This follows easily by induction. The base case b = 1 is obvious from the definition of B . For the induction step, observe that

(Be )uv  = (Be - 1 B)uv  =        (Be - 1 )uw bwv .

w_V

Since all entries of Be - 1  and B are non-negative, the sum on the right hand side is greater than 0 if and only if there exists a vertex w e V such (Be - 1 )uw  > 0 and bwv  > 0. By the induction hypothesis, (Be - 1 )uw  > 0 if and only if there is a π-increasing path of length b _ 1 from u to w .  By definition, bwv  > 0 if and only if there is an edge from w to v, and π(w) < π(v).  These conditions hold simultaneously for some w if and only there is a π-increasing path of length b from u to v .

Observe that G has a π-increasing k-cycle if and only if there exist two vertices u and v such that there is a π-increasing path from u to v of length k _ 1, and (u, v) e E . This suggests the following algorithm. We first compute the matrix C = Bk - 1 . This can be done using k _ 2 matrix multiplications in time O(kn3 ), or using fast exponentiation in time O(log(k)n3 ).  (Or, using both fast matrix multiplication and fast exponentiation in time O(log(k)nω ) for some 2 < ω < 3.) Then we go over all entries of C, and whenever cuv  > 0, we check if (u, v) e E using the adjacency matrix representation of G. This check takes time O(n2 ). If there are u and v such that cuv  > 0 and (u, v) e E, then G has a π-increasing k-cycle. The total running time is dominated by computing C, and is O(kn3 ), or O(log(k)n3 ) using fast exponentiation (or O(log(k)nω ) with fast matrix multiplication).