Reliable assignments of processors to tasks and factoring on matroids. (English) Zbl 0796.68027
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 D. Welsh [Complexity: Knots, colourings and counting, London Mathematical Society Lecture Note Series 186 (1993)].
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 D. Welsh [Complexity: Knots, colourings and counting, London Mathematical Society Lecture Note Series 186 (1993)].
Reviewer: C.McDiarmid (Oxford)
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 68R05 | Combinatorics in computer science |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Agrawal, A.; Barlow, R. E., A survey of network reliability and domination theory, Oper. Res., 32, 478-492 (1984) · Zbl 0544.90049 |
| [2] | Agrawal, A.; Satyanarayana, A., An \(O(|E\)|) time algorithm for computing the reliability of a class of directed networks, Oper. Res., 32, 493-515 (1984) · Zbl 0544.90033 |
| [3] | Ball, M. O.; Provan, J. S., Bounds on the reliability polynomial for shellable independence systems, SIAM J. Algebraic Discrete Methods, 3, 166-181 (1982) · Zbl 0504.05053 |
| [4] | Barlow, R. E., Set theoretic signed domination for coherent structures, (Report ORC 82-1 (1982), Univ. California Berkeley) |
| [5] | Bixby, R. E., The minimum number of edges and vertices in a graph with edge-connectivity \(n\) and mn-bonds, Networks, 5, 253-298 (1975) · Zbl 0314.05106 |
| [6] | Brualdi, R. A., Transversal matroids, (White, N., Combinatorial Geometrics (1987), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 72-97 · Zbl 0294.05018 |
| [7] | Brylawski, T., A combinatorial model for series-parallel networks, Trans. Amer. Math. Soc., 154, 1-22 (1971) · Zbl 0215.33702 |
| [8] | Colbourn, C. J., The complexity of completing partial latin squares, Discrete Appl. Math., 8, 25-30 (1984) · Zbl 0538.05013 |
| [9] | colbourn, C. J., The Combinatorics of Network Reliability (1987), Oxford Univ. Press: Oxford Univ. Press Oxford |
| [10] | Colbourn, C. J., Edge-packings of graphs and network reliability, Discrete Math., 72, 49-61 (1988) · Zbl 0657.90041 |
| [11] | Colbourn, C. J.; Pulleyblank, W. R., Matroid Steiner problems, the Tutte polynomial and network reliability, J. Combin. Theory Ser. B, 41, 20-31 (1989) · Zbl 0618.05017 |
| [12] | Dinic, E. A.; Karzanov, A. V.; Lomonosov, M. V., The minimum cuts’ structure of a graph, (Issledovaniya po diskretnoi optimizaccii (1976), Nauka: Nauka Moscow), 290-306, (in Russian) |
| [13] | Edmonds, J., Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standards, 68, 67-72 (1965) · Zbl 0192.09101 |
| [14] | Holyer, I., The NP-completeness of some edge-partition problems, SIAM J. Comput., 10, 713-717 (1981) · Zbl 0468.68069 |
| [15] | Hopcroft, J.; Karp, R. M., An \(n^{2.5}\) algorithm for maximum matching in bipartite graphs, SIAM J. Comput., 2, 223-231 (1973) · Zbl 0266.05114 |
| [16] | Ingleton, A. W.; Piff, M. J., Gammoids and transversal matroids, J. Combin. Theory Ser. B, 15, 51-68 (1973) · Zbl 0264.05021 |
| [17] | Lomonosov, M. V., Bernoulli scheme with closure, Problemy Peredachi Informatsii, 10, 1, 91-101 (1974), (Russian) · Zbl 0316.05020 |
| [18] | Lomonosov, M. V.; Polesskii, V. P., Lower bounds of network reliability, Problems Inform. Transmission, 8, 118-123 (1972) · Zbl 0335.05124 |
| [19] | Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001 |
| [20] | McDiarmid, C., Strict gammoids and rank functions, Bull. London Math. Soc., 4, 196-198 (1972) · Zbl 0247.05130 |
| [21] | Oxley, J., Graphs and series-parallel networks, (White, N., Theory of Matroids (1986), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0587.05020 |
| [22] | Polesskii, V. P., On a method for constructing reliable communication networks, (Discrete Automata and Communication Networks (1970), Nauka: Nauka Moscow), 13-19, (in Russian) |
| [23] | Provan, J. S.; Ball, M. O., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 777-788 (1983) · Zbl 0524.68041 |
| [24] | Ramanathan, A.; Colbourn, C. J., Counting almost minimum cutsets with reliability applications, Math. Programming, 39, 253-261 (1987) · Zbl 0631.90029 |
| [25] | Satyanarayana, A.; Chang, M. K., Network reliability and the factoring theorem, Networks, 13, 107-120 (1983) · Zbl 0504.90031 |
| [26] | Schrijver, A., Matroids and linking systems, J. Combin. Theory Ser. B, 26, 349-369 (1979) · Zbl 0414.05015 |
| [27] | Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002 |
| [28] | Wood, R. K., A factoring algorithm using polygon-to-chain reductions for computing K-terminal network reliability, Networks, 15, 173-190 (1985) · Zbl 0588.90030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
