<p>I am working on enumerating all the set covers (need not be minimal). A branching algorithm runs in <span class="math-container">$O^*(1.2353^{|U|+|S|})$</span> time that branches on all the sets of size at least three. As the branching algorithms checks all the possible set covers, we have all the set covers. <br> For the sets of size at most two, there is a polynomial time algorithm that computes the set cover of minimum size, as this problem is the same as solving the edge cover problem. But, I want to compute all the possible set covers even when the size of the sets is at most two. I am looking for a polynomial time or sub-exponential time algorithm. It would be helpful if someone could guide me through this. I am interested in enumerating edge covers or set covers of size at most two in some way. <br>
<a href="https://www.cys.cic.ipn.mx/ojs/index.php/CyS/article/view/2244" rel="nofollow noreferrer">This</a> paper seems to count all the edge covers, but i am not sure whether it can be modified to obtain all the edge covers as well.</p>

CC BY-SA 4.0
2023-08-24T16:16:50.443Z
How could you enumerate all set covers of size two in polynomial time, given that there can be exponentially many of them?
Neal Young
CC BY-SA 4.0
2023-08-24T17:32:08.893Z
Sub exponential time algorithm would also work for me.
Balchandar Reddy
CC BY-SA 4.0
2023-08-24T21:58:58.347Z
How could you enumerate all set covers of size two in sub-exponential time, given that there can be exponentially many of them?
Neal Young
<graph-algorithms><np-hardness>
Enumerating all set covers with sets of size at most two
Balchandar Reddy
# Enumerating all set covers with sets of size at most two

(Asked by: username_0 on 2023-08-24)

I am working on enumerating all the set covers (need not be minimal). A branching algorithm runs in $O^\*(1.2353^{|U|+|S|})$ time that branches on all the sets of size at least three. As the branching algorithms checks all the possible set covers, we have all the set covers.   
 For the sets of size at most two, there is a polynomial time algorithm that computes the set cover of minimum size, as this problem is the same as solving the edge cover problem. But, I want to compute all the possible set covers even when the size of the sets is at most two. I am looking for a polynomial time or sub-exponential time algorithm. It would be helpful if someone could guide me through this. I am interested in enumerating edge covers or set covers of size at most two in some way.   
[This](https://www.cys.cic.ipn.mx/ojs/index.php/CyS/article/view/2244) paper seems to count all the edge covers, but i am not sure whether it can be modified to obtain all the edge covers as well.

**Tags:** graph-algorithms, np-hardness

> **Comments:**
> **username_1**: How could you enumerate all set covers of size two in polynomial time, given that there can be exponentially many of them?  
> **username_0**: Sub exponential time algorithm would also work for me.  
> **username_1**: How could you enumerate all set covers of size two in sub-exponential time, given that there can be exponentially many of them?  

---

## 0 answers

