Reliable assignments of processors to tasks and factoring on matroids (Q685664)

Suppose that there is a set of processors, a set of tasks, and a bipartite graph between them indicating which processors can perform which tasks; and suppose that processors fail independently with known probabilities. Certain natural reliability questions can be phrased in terms of the associated transversal matroid on the set of processors. It is shown that counting minimum cardinality circuits in a transversal matroid is \(\# P\)-complete (by a reduction from counting cliques in a graph), and thus that the reliability questions are hard. Then a natural factoring algorithm based on series and parallel reductions is proposed for computing the `span reliability' polynomial of a matroid, and some related inequalities are discussed. For related recent independent work on complexity questions in the `Tutte plane', see for example \textit{D. Welsh} [Complexity: Knots, colourings and counting, London Mathematical Society Lecture Note Series 186 (1993)].