Minimum Pair Wise test set calculation and (possible) connections with Graph Theory

The problem we will engage here is the following: having N variables with different values each one, what is – if exist – a minimal test set allowing a full pair wise coverage? In other words, consider the following table:

A_1 A_2 A_3 A_K
1 1 1   1
2 2 2   2
N1 N2 N3 NK

 K variables with different values each ones

Consider now the ordered sequence (N1, N2, N3, …, NK) where N1 ≥ N2 ≥ N3 ≥ … > NK. We may expect that the minimal pair wise test set has no more and no less than N1●N2 test cases. In the following for “Minimal Pair Wise Test Set” we consider not a generic test set that should be extracted with some kind of algorithm, but the test set for which each variables pairs appears one and only one times. In other words, the frequency map of all variables pair is exactly equal to one. This should be a little importance for practical test problems, but it should be interesting from a theoretical point of view. For example, for the variables and values below:

A_1 A_2 A_3 A_4
1 1 1 1
2 2 2 2
3 3 3  
4 4 4  

4 variables with different values each ones as Example

We forecast a minimum test set is composed by 5●4 = 20 test cases.

Such minimal test cases exist in some particular cases, for example when we have 4 variables with 3 values each one (as we will see in the following paragraph), so the answer to the question should not be always “YES” or always “NO”. Investigating on the problem, using the IPOG algorithm used by NIST ACTS tool, we will find a correlation among: combinatorial pair wise problems, k-partite graph (Graph Theory) and prime number.

As an empirical conjecture (so, not a well-proofed theorem) we will find that there is a solution of the problem (which we will call in the following “Minimal Pair Wise Problem), when:

  • We have N variables with N values or (N+1) variables with N values each.
  • N is prime
  • Finding solution for the Minimal Pair Wise Problem for N variables with N values means find the Hamiltonian Circuits for KN,N,…N (with N indexes) Kuratowski’s graph.
  • The solution for the Minimal Pair Wise Problem for (N+1) variables with N values do not imply the existence of Hamiltonian Circuits for KN,N,…N (with N+1 indexes) Kuratowski’s graph.

Connections between Graph Theory and pair wise testing was already discussed in the article “Pairwise Test Set Calculation using k-partite Graphs” written by Elke Salecker, Sabine Glesner (TU Berlin), 2010 IEEE International Conference on Software Maintenance (ICSM)” but with a different purpose.

For Graph Theory definitions and theorems we referred the book: “Graph Theory, with applications to engineering and computer science “ – Narsingh Deo – PHI Editions.

Attached the complete article, freely downloadable. Welcome to any comments and/or corrections and/or advices.

FileDescriptionFile sizeDownloadsCreated
Download this file ( Pair Wise test set calculation and (possible) connections with Graph Theory756 kB4492015-12-28 09:30