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.

Comments:

Hi,

Good progress in understanding the problem .. But may be there is a long way to find a solution.
I am astonished by the people who resolved it. Personally, I tried and I failed.

Posted by guest on November 13, 2009 at 07:00 PM PST #

Obviously I do not want to spoil it by giving out the solution. The only suggestion I can offer is to think about pruning and do not give up.

Posted by Augustus on November 16, 2009 at 02:58 AM PST #

I think the complexity of TSP is n!/2 because it does not matter which direction in time one takes.
See http://en.wikipedia.org/wiki/Travelling_salesman_problem#cite_ref-0

Where can I find a proof/citation of "2\^m possible subsets of edges in a graph of m edges" ?

Thanks,

Troy

Posted by Troy on December 07, 2009 at 02:53 AM PST #

Nevermind, I figured out how to prove it.

Represent the edges as a binary string, 1 character per edge, 0 = not in, 1 = in

Therefore 2\^m possibilities.

Posted by Troy on December 07, 2009 at 02:58 AM PST #

Re: "pruning techniques", are you referring to tree decomposition?

Posted by Martin on January 13, 2010 at 03:58 AM PST #

Post a Comment:
Comments are closed for this entry.
About

Augustus Franklin Diraviam works for the Solaris Cluster engineering group at Sun Microsystems. He lives in the San Francisco bay area.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today
Bookmarks
Links

No bookmarks in folder

Blogroll

No bookmarks in folder