= Tomography (Graph set covering) =

<<TableOfContents>>

== Problem Description ==

In order to guarantee the quality of communication of a PC network, the network administrator routinely sends out probing messages from the servers to the network. Each probing message is sent to a subset of nodes known as a trace route. Given a set of trace routes of past probing messages, the problem is to find a smallest subset of trace routes that can cover the entire network.

== Predicates ==

 * '''Input''': {{{max_node_num/1, max_traceroute_num/1, traceroute/2}}}

 * '''Output''': {{{sol/1}}}

== Input format ==

In the input, the {{{max_node_num(N)}}} gives the number of nodes in the network (nodes are numbered from 1 to N), the fact {{{max_traceroute_num(M)}}} gives the number of trace routes M (trace outes are numbered from 1 to M), and the predicate traceroute/2 gives the set of trace routes, where a fact {{{traceroute(I,Node)}}} means that the node Node is included in the trace route numbered I.

== Output format ==

The predicate sol/1 gives the set of selected trace routes that covers the entire network, where a fact {{{sol(I)}}} means that the trace route numbered I is selected.

== Example(s) ==

Input: {{{max_node_num(3). max_traceroute_num(3). traceroute(1,1). traceroute(1,2). traceroute(2,2). traceroute(2,3). traceroute(3,1). traceroute(3,2).}}}

Possible output: {{{sol(1). sol(2).}}}

== Author(s) ==
 * Author: Atsuo Tachibana 
   * Affiliation: KDD Labs, Japan     
 * Author: Neng-Fa Zhou 
   * Affiliation: CUNY Brooklyn College and Graduate Center, USA
 * Author: Masato Tsuru 	
   * Affiliation: Kyushu Institute of Technology, Japan