The common practice is to model the Kidney Exchange Problem (KEP) on directed graph G = (V,A), called compatibility graph, where set of vertices V corresponds to the set of incompatible pairs and an arc from a vertex i to a vertex j indicates a compatibility of donor in i with the patient in j.
The instances have been created by the most commonly used generator, described in Saidman S, Roth A, Sönmez T, Ünver M, Delmonico F. Increasing the opportunity of live kidney donation by matching for two-and three-way exchanges. Transplantation2006;81:773–82.
The generator creates random graphs based on probabilities of blood type and of donor–patient tissue compatibility. Default values for the generator's parameters were used.
For the research where probabilities of failure of arcs and vertices are considered, information is provided in an additional file for each instance. The probabilities of failure p_i of a vertex i, or p_ij of an arc (i,j) were generated randomly with uniform distribution in [0;1].
The dataset is split into two parts, according to the size of the graphs. The folder small contains instances with n = 20,30,40,50,60,70,80,90 and100 vertices. There are 50 instances of each size. for instances with n = 20,30,40,50,60,70,100 vertices and 10 instances of bigger sizes. The folder big has instances with n = 100, 200,300,400,500,600,700,800,900,1000,2000, 3000,5000 vertices, with 10 instances of each size.
Each instance has two files with data.
1) The first one is the compatibility graph of an instance of a given size. Name of those files is formed as n_seed.input.gz
where n = |V| is the number of incompatible pairs in the pool and seed is the seed, used for random function when generating the instance.
In the first line the file contains values n – number of vertices in the graph and m – number of arcs in the graph. In the following m lines of the file the existing arcs (i,j) are presented as follows:
i j w-ij
where w_ij is the weight of the arc, which is always equal to 1.0 for all the instances in this dataset.
2) The second file contains probabilities of failure. Name is formed as
n_seed.prob.gz
The lines of the file formed as follows. Consecutively for each vertex i in V:
p_i
p_ij1… pi_jk
where (i, j1)… (i,jk) is the set of outgoing arcs for vertex i.