Tomography (Graph set covering)

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