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