Hello there,

I am postgraduate student of Dublin City University, Ireland, in the field of VLSI Testing. I am currently working on some heuristics and I need a probability formula. I want to get an expert's point of view in my matter. Say there is an initial list of so called tests: T1, T2, T3, ..., Tn Every test element Ti of the above list has a list of compatibility (incompatibility), which includes all the elements (tests) from the initial list, the Ti test is compatible (incompatible) with. For example, say the initial list is: {T1, T2, T3, T4, T5, T6, T7, T8, T9, T10} and the compatibility lists of these elements (tests) are:

T1 compatible with {T2, T3, T5, T6, T8, T9} T2 compatible with {T1, T3, T7, T8}
T3 compatible with {T1, T2, T4, T7, T9, T10} T4 compatible with {T3, T5, T7, T8}
T5 compatible with {T1, T4, T9, T10}
T6 compatible with {T1, T7, T8, T9}
T7 compatible with {T2, T3, T4, T6, T8, T9}
T8 compatible with {T1, T2, T4, T6, T7, T9, T10}
T9 compatible with {T1, T3, T5, T6, T7, T8, T10}
T10 compatible with {T3, T5, T8, T9}

If Ti is compatible with Tj then Tj is compatible to Ti. That is, if Tj belongs to Ti's compatibility list then Ti belongs to Tj's compatibility list too!

This problem is part of an algorithm and for complexity reasons it was concluded that the probabilistic way is computationaly less expensive thus giving "cheaper" near-optimal solutions. Therefore, only the number of elements from the compatibility list of every test Ti would be considered for the calculation of the compatibility (incompatibility) probability between any two randomly selected elements (tests) from the initial list.

Question 1: What is the compatibility (incompatibility) probability between any two elements (tests) Ti and Tj randomly selected from the initial list knowing only the number of elements from their compatibility (incompatibility) lists?

For the above example, say what's the compatiblity (incompatibility) probability between T3 and T6 in the above example knowing that T3 has 6 elements in its compatibility list while T6 has 4 elements?

Question2: (a generalization of the first question) Say a number of elements (tests) are already selected from the initial list at a certain moment. What are the compatibility (incompatibility) probabilities between any one of them to be (simultaneously) compatible to the rest of the elements selected in the above mentioned set (knowing only te number of compatible elements from the compatibility list of each element). That is, for example, T1 is compatible (simultaneously) to T4, T6 and T8 if and only if T1 it is compatible at the same time to T4, to T6, and to T8. Shortly what is the compatibility (incompatibility) probability between T1 and the rest of the selected elements set?

I would appreciate if you could give me the probability formula and if possible a middle level explanation of the reasoning. I look forward to your answer.

Best regards, Valentin Muresan

The problem is equivalent to the following. Construct a graph with a vertex for each test and put an edge between two vertices if and only if the two vertices represent compatible tests. The degree of a vertex is the number of edges incident with it. The question amounts to asking, given the set of degree values only (the degree sequence), what is the probability that vertex i and vertex j are joined? If all the degrees were the same it wouldn't be too hard but there is no such assumption. In general I do not think that the answer is known. I do believe that there are algorithms that will generate random graphs on n points given their degree sequence but I have not analyzed them. Are there any graph theorists in Dublin City University's math department? They may be able to help.