On enumerating all minimal solutions of feedback problems. (English) Zbl 1004.68122
Summary: We present an algorithm that generates all (inclusion-wise) minimal feedback vertex sets of a directed graph \(G= (V,E)\). The feedback vertex sets of \(G\) are generated with a polynomial delay of \(O(|V|^2(|V|+|E|))\). We further show that the underlying technique can be tailored to generate all minimal solutions for the undirected case and the directed feedback arc set problem, both with a polynomial delay of \(O(|V||E|(|V|+|E|))\). Finally, we prove that computing the number of minimal feedback arc sets is \(\#\)P-hard.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | M. Bidjan-Irani, U. Glässer, F. Rammig, Knowledge based tools for testability checking, in: Proceedings of the third International Conference on Fault-Tolerant Computing Systems, September 1987.; M. Bidjan-Irani, U. Glässer, F. Rammig, Knowledge based tools for testability checking, in: Proceedings of the third International Conference on Fault-Tolerant Computing Systems, September 1987. |
| [2] | Diaz, M.; Richard, J. P.; Courvoisier, M., A note on minimal and quasi-minimal essential sets in complex directed graphs, IEEE Trans. Circuit Theory, 19, 512-513 (1972) |
| [3] | R. Floyd, Assigning meaning to programs, in: Proceedings of Symposium on Applied Mathematics, American Mathematical Society, 1967, pp. 19-32.; R. Floyd, Assigning meaning to programs, in: Proceedings of Symposium on Applied Mathematics, American Mathematical Society, 1967, pp. 19-32. · Zbl 0189.50204 |
| [4] | E. Fredkin, Trie memory, Comm. ACM 3 (1960) 490-499.; E. Fredkin, Trie memory, Comm. ACM 3 (1960) 490-499. |
| [5] | Gusfield, D., A graph theoretic approach to statistical data security, SIAM J. Comput., 17, 552-571 (1988) · Zbl 0653.90039 |
| [6] | D.S. Hochbaum, Various Notions of Approximations: Good, Better, Best and More, PWS Publishing, Boston, MA, 1995, p. 350. (Chapter 9).; D.S. Hochbaum, Various Notions of Approximations: Good, Better, Best and More, PWS Publishing, Boston, MA, 1995, p. 350. (Chapter 9). |
| [7] | Johnson, D. S.; Yannakakis, M.; Papadimitriou, C. H., On generating all maximal independent sets., Inform. Process. Lett., 27, 119-123 (1988) · Zbl 0654.68086 |
| [8] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York, London), 85-103 · Zbl 0366.68041 |
| [9] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput., 9, 558-565 (1980) · Zbl 0445.68054 |
| [10] | Leung, J. Y.-T.; Lai, E. K., On minimum cost recovery from system deadlock, IEEE Trans. Comput., 28, 671-679 (1979) · Zbl 0414.68019 |
| [11] | Linial, N., Hard enumeration problems in geometry and combinatorics, SIAM J. on Algebraic and Discrete Methods, 7, 331-335 (1986) · Zbl 0596.68041 |
| [12] | Lucchesi, C.; Younger, D., A minmax relation for directed graphs, J. London Math. Soc., 17, 369-374 (1978) · Zbl 0392.05029 |
| [13] | Pardalos, P. M.; Xue, J., The maximum clique problem, J. Global Opt., 301-328 (1994) · Zbl 0797.90108 |
| [14] | E.M. Reingold, J. Nievergelt, N. Deo, Combinatorial Algorithms: Theory and Practice, Prentice-Hall, Englewood Cliffs, USA, 1977 (Chapter 8).; E.M. Reingold, J. Nievergelt, N. Deo, Combinatorial Algorithms: Theory and Practice, Prentice-Hall, Englewood Cliffs, USA, 1977 (Chapter 8). · Zbl 0367.68032 |
| [15] | Shioura, A.; Tamura, A.; Uno, T., An optimal algorithm for scanning all spanning trees of undirected graphs, SIAM J. Comput., 26, 678-692 (1997) · Zbl 0870.05066 |
| [16] | Smith, G.; Walford, R., The identification of a minimal feedback vertex set of a directed graph, IEEE Trans. Circuits and Systems, 9-15 (1975) |
| [17] | E. Speckenmeyer, On feedback problems in digraphs, in: M. Nagl (Ed.), Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, Castle Rolduc, The Netherlands, Springer, Berlin, Lecture Notes in Computer Science, Vol. 411, 1989, pp. 218-231.; E. Speckenmeyer, On feedback problems in digraphs, in: M. Nagl (Ed.), Proceedings of the 15th International Workshop on Graph-Theoretic Concepts in Computer Science, Castle Rolduc, The Netherlands, Springer, Berlin, Lecture Notes in Computer Science, Vol. 411, 1989, pp. 218-231. · Zbl 0768.68181 |
| [18] | Squire, M. B., Generating the acyclic orientations of a graph, J. Algorithms, 26, 275-290 (1998) · Zbl 0894.68106 |
| [19] | Srimani, P. K., Enumeration of all minimum feedback edge sets in a directed graph, Int. J. Systems Sci., 11, 239-246 (1980) · Zbl 0428.05034 |
| [20] | Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all the maximal independent sets, SIAM J. Comput., 6, 505-517 (1977) · Zbl 0364.05027 |
| [21] | Wang, C.; Lloyd, E.; Soffa, M., Feedback vertex sets and cyclically reducible graphs, J. ACM, 32, 296-313 (1985) · Zbl 0633.68064 |
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.
