Facebull Problem Definition

I mentioned earlier that the puzzle named “Facebull” in Facebook, is a variation of the traveling salesman problem. Let us define the facebull problem more formally and see if it is really true.

As I mentioned before, this problem can be modeled as a graph problem, where every chemical compound is a vertex and every machine is a directed edge in the graph. The cost of the machine is the weight of the edge in the graph. In this model, the following information is given in the problem definition.

  • The given graph is a weighted strongly connected directed graph, because every vertex can be reached from any other vertex.
  • The given graph need not be a fully connected graph, because every pair of vertices need not have a edge.

Now, the following are the unknowns,

  • We want to find the set of edges among the given set of edges, such that every vertex can still be reached from any other vertex.
  • When there are multiple such subsets, we want to find the subset that is the minimum weight sum of its edges.

Thus facebull(FB) problem can be stated concisely as below.

Given a strongly connected directed graph G = (V, E) with vertex set V and weighted edge set E, find the strongly connected subgraph G’ = (V, E’), with E’ ⊆ E having minimum total weight.

The definition of a asymmetric travelling salesman problem(TSP) is as below.

Given a fully connected directed graph, find the minimum cost tour that visits every vertex exactly once and returns to the starting vertex.

A tour that visits every vertex of a graph exactly once is also known as a hamiltonian cycle.

Any fully connected graph is also strongly connected, so the inputs to TSP and FB could be the same graph. Usually in a real TSP the distances between the vertices are Euclidean distances, this is not true for the FB problem.

The main difference between the TSP and the FB problem is the unknown in the problem. In TSP, the unknown is a cycle in the graph. In FB problem, the unknown is a set of edges, with the only constraint that the resultant graph be strongly connected. Another key difference is, every time a edge is used in a TSP solution, a cost is added to the solution. However, a edge that is added to the FB solution is a machine that is bought and therefore could be used multiple times at no cost.

Finally, consider the computational complexity of TSP and the FB problem. TSP belongs to the class of NP-Hard problems, it is O(n!) in its worst case, where n is the number of vertices of the graph. For a graph of 12 nodes, the program must consider 12! = 479001600 possibilities. A brute force solution that considers all the possibilites for a graph of 20 nodes, will take many years to complete!

There are 2^m possible subsets of edges in a graph of m edges. Therefore, the complexity of FB is 2^m, where m is the number of edges of the graph. If the given graph is fully connected, m = n², where n is the number of nodes. Therefore FB is O(2^n²) is its worst case. For a graph of 12 nodes, a solution to FB must consider 22300745198530623141535718272648361505980416 possibilites. O(2^n²) is worse than O(n!).  FB is a harder problem than TSP!

Another way of saying this is, the size of the search space for a FB solution is 2^m.  The solution can be any where within that space, so any correct algorithm must guarantee to be able to find the solution any where in that space. An algorithm can restrict the size of its search space, but only if it can prove that the solution cannot be in the unsearched area. I will talk more about some of these pruning techniques in a future blog entry.

[cross posted from my Sun Blog]

Intellectual Dessert

The excitement of learning separates youth from old age. As long as you’re learning you’re not old.” – Rosalyn Yalow

One of my most enjoyable activity at Sun is to have “intellectual dessert”. Intellectual Dessert is the name given to a series of regular talks and presentations in Sun on varied topics from experts in different fields. These talks provide opportunity for any Sun employee to interact with many smart people and know about work in other related areas. I have attended talks all the way from Rupert Sheldrake on his controversial morphic resonance theory, to talks by Turing award winners, like John McCarthy on the evolution of intelligence and Vinton Cerf on bit rot. Recently I enjoyed a talk by Nobel prize winner, Martin Perl on developing creativity in science.

I learnt recently that the talks at Palo Alto Research Center(PARC) is open to the public too. This is also a weekly forum with discussions on varied topics. The talk this Thursday is about the adventures of Cuil, a startup in the world of search engines. I plan to drive over to Palo Alto for my first visit to the PARC Forum.