Complexity of listing all minimal cut sets / connected 2-partitions of a graph I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm that ideally would have the complexity linear in the number of cut sets, however, I only find papers describing algorithms that would generate all minimal cut sets between a fixed vertex pair. I would then have to run any algorithm for each pair and remove duplicates, so I am searching for a better approach. Does someone of you know any upper/lower bounds of the complexity of this problem (or even better, an optimal algorithm)? I would also be interested in results concerning special graphs, e.g. max degree k or so.

Best,
Vany
dear all. There is no contradiction here. The problem of listing or enumerating all cutsets is a counting problem which is #P-hard. The class #P consists of all the problems that can be solved by a non-deterministic counting Turing machine in polynomial time. Therefore, the class #P is useful for classifying counting problems. On the other hand, the class NP is suitable for classifying  decision problems. A decision version of your problem would be, for instance: Is there a cutset with cardinality less than $k$? Obviously, if you can enumerate all the cutsets in polynomial time, then you can also say in polynomial time if there exists a cutset with cardinality less than $k$. In other words, the counting version is at least as hard as the decision version.  Therefore, if a counting problem is #P-hard, then it is NP-hard (I am talking about the same counting problem, not its decision version). However, the converse is an open question. In other words, for the time being, saying that this problem is #P-hard is a stronger statement than saying that it is NP-hard.