Meet in the middle

Cosmin Negruseri
10 august 2012

Meet in the middle (sometimes called split and merge) is a clever approach which tries to trade off space for time.

Let’s discuss a few applications.

Bidirectional search(interview question)

Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the web graph of the facebook friendship graph, find out the shortest path between them.

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is k and the average branching factor in the network is p then we explore O(p^{(k/2)) nodes instead of O(p}k) nodes.

Friend of a friend problem (inteview question)

Given two user names in a social network find an easy way to test if they one is a friend of a friend of the other.

A trivial solution is to find first the list of friends for the first user and then the lists of friends for each of his friends. Assuming the network has an average degree of k, this approach does k + 1 requests.
A somewhat faster solution is to do some preprocessing and store for each user a hash set of its friends of friends. The number of requests is 1 now but space used is O(nk^{2) and the size of a reply is O(k}2).
A better solution uses the meet in the middle approach: we issue two queries, one for the friends of the first user and one for the friends of the second user. Then we intersect the two sets. Now we use just 2 requests, the graph takes O(nk) space, and the reply sizes are O(k).

Meet in the middle attack (not to be confused with man in the middle attack)

DES is a encryption standard which uses 56 bit keys. This was enough when the algorithm got invented but currently computers can use a brute force approach to break the encryption. One simple idea to make the encryption more secure is to apply the encryption twice using two different keys. This approach is susceptible to the meet in the middle attack developed by Diffie Hellman. So currently 3DES is used which uses three keys and encrypts the message three times.

Let’s see why 2DES is bad. We call Ek the encryption function using the secret key k and Dk the decryption function using the secret key k. 2DES uses Ek1) = s to encrypt and Dk2) = p to decrypt.

Diffie Hellman’s meet in the middle attack trades of space for time to find out the two secret keys.
For the pattern p it tries all the possible keys to obtain a set of numbers corresponding Ek(p). Also for the pattern s it uses all the possible keys to decrypt s, Dk(s).
If we find any match in the two sets it means that Ek1 = Dk2 so the secret keys are k1 and k2.
The naive brute force algorithm would go through 2^{56 * 2}56 iterations by brute forcing through all possible values of k1 and k2 while this algorithm uses 2^{56 * 56 memory to store Ek(p) and does O(2}56) work to find a match.

drawing
h2. a + b + c + d + e = f

Given an array, find out if there are any 6 numbers such that the sum of the first five equal to the 6th (you can use the same number more than once).

The naive algorithm is O(N^{6) try all the possible combinations of 6 numbers. A less naive algorithm brute forces through all n}5 combinations of 5 numbers and then efficiently checks if their sum is in the original array by using a hash table.
But by now you’ve probably started thinking how meet in the middle can be applied for this problem. The trick is to rewrite the equation as a + b + c = f - d - e. Store all the n^{3 sums a + b + c in a hash set S. Then iterate through all n}3 combinations for d, e, f and check if S contains f - d - e. This algorithm has O(n^3) time and space complexity.

the discrete logarithm problem

Given n a prime number and p, q two integer numbers between 0 and n-1 find k such that p^k = q modulo n.
The baby step, giant step uses the meet in the middle principle.
We can write k = i ([sqrt(n)] + 1) + j.
Notice that i <= sqrt(n) and j <= sqrt(n).
Now our equality looks like this p ^{(i ([sqrt(n)] + 1) + j) = q modulo n. We can divide by p}j and get p^{(i[sqrt(n)] + 1) = qp}-j modulo n.
Now the application of meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a match.
This algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.

Minimal vertex cover

Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the graph has at least one node inside the set.

As before we split the nodes in half. We’ll brute force the set of vertices that are in the first half of the nodes and in a minimum vertex cover. For edges (f, s) where node f is in the first half but not in our picked set and s in the second half we have to use s to cover the edge. Now we’re left with edges that have both end nodes in the second half. We compute the minimum edge cover for each induced subgraph. O(3^n).

Additional problems

1. (Equal partition) Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal.
2. (Maximum independent set) Given a graph of 30 vertices. Find a set that contains the most number of nodes such that no two nodes in the set are connected by an edge.

Try the to solve these two problems in the comment section.