Summary of complexities of enumeration problems

（準備中）（Work in progress） We will describe the results of complexities of enumeration problems

• (Minimal dominating set) and (minimal hitting sets) are equivalent [M. M. Kanté, V. Limouzy, A. Mary and L. Nourine, "On the enumeration of minimal dominating sets and related notions.", SIAM Journal on Discrete Mathematics, vol.28, no.4, pp.1916-1929, 2014]
• (Minimal dominating set) and (total minimal dominating sets) are equivalent [M. M. Kanté, V. Limouzy, A. Mary and L. Nourine, "On the enumeration of minimal dominating sets and related notions.", SIAM Journal on Discrete Mathematics, vol.28, no.4, pp.1916-1929, 2014]
• If there is an output-polynomial time algorithm for enumerating (minimal connected vertex covers on bipartite graph), then there is an output-polynomial time algorithm for enumerating (minimal transversal in hypergraphs) [Y. Kobayashi, K. Kurita, Y. Matsui and H. Ono, "Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.", arXiv preprint arXiv:2308.16426, 2023]
• If there is an output-polynomial time algorithm for enumerating (minimal connected dominating sets on co-bipartite graphs), then there is an output-polynomial time algorithm for enumerating (minimal transversal in hypergraphs) [Y. Kobayashi, K. Kurita, Y. Matsui and H. Ono, "Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.", arXiv preprint arXiv:2308.16426, 2023]