= Tomography Problem =

Given a graph and a set of paths Ps, find a minimum subset of Ps that covers the nodes of the graph.

The problem is similar to the set covering problem.

As can be seen by the example below, a path is a set of nodes, and paths may overlap.

A path has to be encoded with with facts. For example, path([0,4,1]) can be encoded as
    
 * path(1,0).
 * path(1,4).
 * path(1,1).

Where the first argument is a path number and the second argument is a node in the path.


== Example ==

path([0,4,1]).
path([0,2]).
path([0,3]).
path([0,4]).
path([0,5]).
path([0,5,6]).
path([0,7]).
path([0,7,8]).
path([0,9]).
path([1,4,0]).
path([1,2]).
path([1,3]).
path([1,4]).
path([1,4,5]).
path([1,6]).
path([1,8,7]).
path([1,8]).
path([1,4,0,9]).
path([2,0]).
path([2,1]).
path([2,0,3]).
path([2,0,4]).
path([2,0,5]).
path([2,0,5,6]).
path([2,7]).
path([2,7,8]).
path([2,9]).
path([3,0]).
path([3,1]).
path([3,0,2]).
path([3,4]).
path([3,5]).
path([3,5,6]).
path([3,8,7]).
path([3,8]).
path([3,0,9]).
path([4,0]).
path([4,1]).
path([4,0,2]).
path([4,3]).
path([4,5]).
path([4,6]).
path([4,3,8,7]).
path([4,3,8]).
path([4,0,9]).
path([5,0]).
path([5,4,1]).
path([5,0,2]).
path([5,3]).
path([5,4]).
path([5,6]).
path([5,0,7]).
path([5,3,8]).
path([5,0,9]).
path([6,5,0]).
path([6,1]).
path([6,5,0,2]).
path([6,5,3]).
path([6,4]).
path([6,5]).
path([6,5,0,7]).
path([6,5,3,8]).
path([6,5,0,9]).
path([7,0]).
path([7,8,1]).
path([7,2]).
path([7,8,3]).
path([7,8,3,4]).
path([7,0,5]).
path([7,0,5,6]).
path([7,8]).
path([7,0,9]).
path([8,7,0]).
path([8,1]).
path([8,7,2]).
path([8,3]).
path([8,3,4]).
path([8,3,5]).
path([8,3,5,6]).
path([8,7]).
path([8,7,0,9]).
path([9,0]).
path([9,0,4,1]).
path([9,2]).
path([9,0,3]).
path([9,0,4]).
path([9,0,5]).
path([9,0,5,6]).
path([9,0,7]).
path([9,0,7,8]).



== Comment ==

This benchmark was by Atsuo Tachibana.


== Author(s) ==

 * Atsuo Tachibana 
   * KDD Labs, Japan     
 * Neng-Fa Zhou 
   * CUNY Brooklyn College and Graduate Center, USA
 * Masato Tsuru 	
   * Kyushu Institute of Technology, Japan